2018-02-14
394
Избыточность кода определяется величиной (n –всего, k – информационных, r –проверочных)
Кстати, имеется еще скорость передачи кодовых комбинаций
Кодовое расстояние. Различие между i -ым и j -ым кодовыми словами (комбинациями) определяется расстоянием dij -числом букв (символов), которыми отличаются в одноименных позициях кодовые слова. Минимальное расстояние между кодовыми словами данного кода называется кодовым (Хэмминговым) расстоянием:
Ошибка не будет обнаружена, если принятый искажённый ИМ можно отождествить с одной из разрешённых кодовых комбинаций, до которой расстояние от принятой комбинации является минимальным.
По значению dk можно определить возможности кода:
dk = 2eи + eо + 1, eи < eо,
где eи - кратность исправляемых кодом ошибок;
eо - кратность обнаруживаемых кодом ошибок.
Т.е. при dk обнаружатся 2eи + eо ошибок и из них 2eи исправятся, остальные eо только обнаружатся.
Пример: при dk = 5 можно
eо = 4 и eи = 0;
eо = 2 и eи = 1 (не из тех двух, eо = 2, а еще кроме них);
|
|
|
eо = 0 и eи = 2.
Или, еи ≤ (dk – 1) / 2
ео ≤ dk – 1
Увеличение избыточности при неизменном числе информационных символов приводит к увеличению кратности исправляемых ошибок, т.е. к повышению помехоустойчивости.
Данные коды называют корректирующими или помехоустойчивыми.
Вес ω кодовой комбинации – количество ненулевых символов в кодовой комбинации.
Весовая характеристика кода W(ω) − количество кодовых комбинаций веса ω.
Кстати: кодовое расстояние между двумя кодовыми комбинациями равно весу их суммы (разности) по модулю 2. Проверить!
Это очень важное свойство. Оно позволяет определить кодовое расстояние кода, не прибегая к сравнению всех пар кодовых комбинаций.
Найдем в коде кодовую комбинацию с минимальным ненулевым весом. По выше приведенному свойству её вес равен кодовому расстоянию некоторых кодовых комбинаций кода. И не существует в данном коде кодовых комбинаций с меньшим кодовым расстоянием, т.к. это означало бы наличие кодовой комбинации с меньшим весом, но мы нашли кодовую комбинацию с минимальным весом. следовательно минимальный ненулевой вес кодовой комбинации равен кодовому расстоянию кода.
Кодовое (Хэммингово) расстояние кода равно минимальному весу его ненулевых кодовых комбинаций!
Хэммингово расстояние также называется Хэмминоговой метрикой. Она удобна для нахождения расстояния между кодовыми комбинациями двоичного кода, хотя может применяться и для q > 2.
Для кодов с q > 2 существует более точная метрика –Ли.
Вес Ли набора 
длины n,где элементы ai выбираются из множества 
, а q – произвольное положительное число, определяется как
|
|
|
где
.
Расстоянием Ли между двумя наборами длины n называется вес Ли разности этих наборов. При q = 2 и q = 3 расстояние Ли и расстояние Хэмминга совпадают; при q > 3 расстояние Ли между двумя наборами больше или равно расстоянию Хэмминга между этими наборами.
Пример. Пусть q = 5 и n = 6. Тогда расстояние Ли между двумя наборами
a = (2 0 0 2 3 4) и b = (2 0 4 0 0 0)
равно весу набора, составленного из разностей соответствующих компонент по модулю 5 (здесь в третьем разряде 0-4=5-4=1):
а — b = (001234).
Таким образом,
ωL(а-b) = 0 +0+1+2 + 2 + 1=6.
Наиболее глубоко изучены и широко используются линейные корректирующие коды. Их изучение и является целью занятия.
