Р е ш е н и е. Нумерация информационных разрядов кода Хэмминга (7, 4) определяет значения разрядов заданного кодового слова следующим образом: а7 а6 а5 а4

Нумерация информационных разрядов кода Хэмминга (7, 4) определяет значения разрядов заданного кодового слова следующим образом:

В соответствии с равенствами (2.11) вычислим значения синдрома:

Получили ненулевое значение синдрома:

С=(с₃с₂с₁)=(110)₂=6₁₀,

следовательно, ошибка произошла в шестом разряде. Исправим ошибку, сложив поразрядно по модулю 2 полученную комбинацию кода Хэмминга (7, 4) с соответствующим вектором ошибки:

.

Ответ: Верная комбинация помехоустойчивого кода Хэмминга (7, 4) имеет следующий вид:

Проведем проверку скорректированного кодового слова в соответствии с системой равенств (2.11):

Нулевое значение синдрома С=(с₃с₂с₁)=000 свидетельствует о том, что комбинация 0110011 скорректирована верно.

2.5.2. Исправление всех двойных и одиночных ошибок (код 8, 2)

При составлении таблицы опознавателей следует иметь в виду, что синдром двойной ошибки равен сумме по модулю 2 синдромов одиночных ошибок. С учётом этого обстоятельства значения синдромов представлены в таблице 4.

Таблица 4 - Таблица синдромов для кода,

исправляющего все одиночные и двойные ошибки

Пояснения: Таблица строится таким образом, чтобы каждому последующему разряду сопоставить опознаватель с минимальным номером. Как и для одиночной ошибки, разрядам 1 и 2 сопоставляются те же синдромы (таблица 2, столбец «Синдром»). Третьему разряду сопоставить синдром 0000011 нельзя, т. к. этот синдром соответствует двойной ошибке в разрядах 1 и 2. Аналогично нельзя использовать синдромы 0000110 и 0000101. Ошибке в разряде 4 нельзя сопоставить код 0000111, т. к. синдром двойной ошибки (например, в 1 и 4 разрядах) в этом случае будет иметь код 0000001 0000111=0000110, т. е. будет совпадать с синдромом ошибки одновременно в разрядах 2 и 3. Остальные синдромы построены, исходя из аналогичных рассуждений (в таблице 4 приведены значения синдромов для одиннадцати разрядов).

Для исправления всех одиночных и двойных ошибок возможны коды (5, 1), (8, 2), (11, 4) и так далее. Эти коды уже не являются плотноупакованными.

Построим для примера код (8, 2), исправляющий все одиночные и двойные ошибки.

Так как n=8, усечем таблицу 4 на восьмом разряде (строка 8), столбец c₇ в этом случае является ненужным.

Отметим, что в таблице 4 первый разряд синдрома с₁ принимает единичное значение в случаях, когда происходит одиночная ошибка в разрядах 1, 5, и 8.

Аналогично можно провести анализ для остальных пяти разрядов и построить следующие равенства:

(2.13)

Проверочные равенства (2.13) определяют значения разрядов синдрома на приемном конце системы связи. Если значение синдрома С=(с₆с₅с₄с₃с₂с₁) отлично от нуля, при одиночной ошибке его значение совпадет с одним из синдромов таблицы 4; таким образом, одиночная ошибка будет опознана и исправлена. При ошибке в двух разрядах необходимо вычислить сумму по модулю 2 двух синдромов из таблицы 4, совпадающую по значению с синдромом С, вычисленным согласно (2.13), и внести коррекцию в соответствующие два разряда искаженной кодовой комбинации.

В соответствии с (2.13) правила построения кода на передающем конце определяются следующими соотношениями:

(2.14)

Каждый из разрядов а₁, а₂, а₃, а₄, а_6, а₇ входит только в одно из проверочных равенств (2.13), поэтому целесообразно выбрать их в качестве проверочных (контрольных) разрядов, а разряды а₅ и а₈ - в качестве информационных.

Отметим, что для исправления всех двойных ошибок, согласно (2.2), минимальное кодовое расстояние (по Хэммингу) равно d_min=2×2+1=5 и, кроме того, согласно (2.1), этот код может также использоваться для обнаружения ошибок кратности от одной до четырех.

Поиск по сайту: