Коды с обнаружением и исправлением ошибок. Код Хемминга
Код Хемминга относится к блоковым кодам. Наиболее простой код, исправляющий ошибки кратности t=1, имеет кодовое расстояние d=3.
Принцип построения
1. На передающей стороне к k информационным символам добавляется r проверочных символов. Значения проверочных символов (0 или 1) определяются путем проверок на четность [2]. В проверку на четность включают определенные элементы кодовых комбинаций, образующие проверочную группу. Сформированный n-разрядный код, состоящий из k информационных и r проверочных элементов, передается в линию связи.
2. На приемной стороне в тех же проверочных группах производится r проверок на четность.
3. Проверочные группы строятся таким образом, чтобы записи результатов каждой проверки 
в двоичной форме давали бы r-разрядное двоичное число 
, указывающее номер разряда (в исчислении с основанием 10) искаженного элемента. Это r-разрядное двоичное число 
называют синдромом ошибки.
Для того чтобы обнаружить и исправить все ошибки кратности 1, число проверочных символов выбирается из соотношения 
. Добавление слагаемого +1 соответствует случаю отсутствия ошибок.
Число элементов помехоустойчивой кодовой комбинации определяется из решения уравнения относительно n:
. (6)
Изначально известно число k. Определив n из уравнения (6), получим число проверочных разрядов r в новых кодовых комбинациях (табл. 2).
|
|
|
Таблица 2. Соотношение числа информационных и проверочных разрядов
| k | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| n | 5 | 6 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 17 |
| r | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
|
|
Выбор значений и позиций проверочных элементов
Если ошибок нет, то синдром ошибки имеет значение 00…00.
При наличии ошибки двоичный код синдрома ошибки должен указать номер разряда кодовой комбинации (в исчислении с основанием 10), в котором произошло искажение элемента.
Единица в первом разряде синдрома ошибки появляется при искажении любого нечетного разряда кодовой комбинации.
Таким образом, в первую проверку должны войти все нечетные элементы принятой кодовой комбинации
. (7)
То есть в первую проверку должны входить все элементы кодовой комбинации, в первом (младшем) разряде которых содержится 1. Если 
, то один из элементов искажен.
Аналогично во вторую проверочную группу должны входить все элементы кодовой комбинации, во втором разряде которых содержится 1.
(8)
Если S2=1, то один из элементов искажен.
|
|
|
Третья проверочная группа содержит элементы, принимающие значение 1 в третьем разряде новой кодовой комбинации:
. (9)
Четвертая проверочная группа содержит элементы, принимающие значение 1 в четвертом разряде новой кодовой комбинации:
. (10)
Проверочные элементы каждой кодовой комбинации должны входить только в одну проверку. Таким образом, проверочными должны быть символы, расположенные в 1-м, 2-м, 4-м, 8-м и т. д. (16-м, 32-м,…) разрядах полученной кодовой комбинации.
Обозначим проверочные символы как 
. Тогда
; 
; 
; 
. (11)
Пример:
1 0 1 0 1 1 – исходная кодовая комбинация (младший разряд слева), число разрядов k=6. Обозначим их как k1, k2, k3, k4, k5, k6.
По табл. 1 найдем число проверочных символов r=4. Помехоустойчивая кодовая комбинация должна содержать n=k+r=10 элементов (разрядов).
Для нахождения проверочных элементов используем вспомогательную схему (а1 – младший разряд), представленную в виде табл. 3:
Таблица 3. Нахождение проверочных элементов
| k1 | k2 | k3 | k4 | k5 | k6 | ||||
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 |
| b1 | b2 | b3 | b4 |
|
|
|
Выполним проверку на четность по описанным выше правилам [выражения (7)-(10)], подставляя в табл. 3 на места ai соответствующие значения символов исходной кодовой комбинации ki и учитывая обозначения (11).
Результаты определения значений проверочных элементов:
;
;
;
.
Подставим в соответствии с табл. 3 на места ai соответствующие значения проверочных элементов bi и значения символов исходной кодовой комбинации ki. Получим новую кодовую комбинацию 0111010011, содержащую информационные символы и проверочные символы.
Пусть принят код 0111110011, т. е. произошла ошибка в 5-м разряде.
Проверочные группы на приемной стороне дадут следующие результаты:
;
;
;
.
Таким образом, синдром ошибки
, то есть, выявлена ошибка в символе 
.
Для ее исправления надо выполнить операцию суммирования а5 с 1 по модулю 2: а5= а5 
1.
Дата добавления: 2020-01-07; просмотров: 587; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!