Синдром одиночных искажений

Комбинация искажения	Номер искаженного элемента	Синдром

Как видно из приведенной таблицы кодовая комбинация синдрома указывает на искаженное место разрешенной кодовой комбинации. Например, если искажен пятый разряд разрешенной кодовой комбинации, то его синдром определится как 0101.

Преобразование исходных двоичных кодовых комбинаций во множество кодов Хэмминга целесообразно рассмотреть на конкретном примере.

Пример. Цель преобразования - составить Np=2ⁿ=60 разрешенных кодовых комбинаций Хэмминга, обнаруживающих и исправляющих одиночные искажения (t=1, S=1).

Методика решения.

1. Определение минимального кодового расстояния

d_min=t+S+1=1+1+1=3.

2. Определение общего числа элементов кодовых комбинаций Хэмминга - n.

N_p £ ; 60 £

Из последнего неравенства определяется общее число элементов кодовых комбинаций Хэмминга n=10.

3. Определение числа информационных элементов k

2^k = 60 k @ 6.

4. Определение числа проверочных элементов r

r = n - k = 10 - 6 = 4.

5. Построение производящей матрицы кода G_10,6 (10 столбцов, 6 строк). Для чего из состава 2^r = 2⁴ =16 проверочных комбинаций для построения производящей матрицы выбирается k=6 любых комбинаций с весом p ³ d_min- 1 = 3 - 1 = 2, например: 0011, 0101, 0110, 0111, 1001, 1010. Производящая матрица имеет вид:

G10,6 = 0

6. Построение проверочной матрицы на основании производящей матрицы G_10,6. Для чего в первую строку проверочной матрицы H_10,6 вписывается первый столбец кортежа проверочных элементов производящей матрицы G_10,7 (000011) и к нему справа приписывается первая строка единичной матрицы (1000), во вторую строку проверочной матрицы вписывается кортеж второго столбца производящей матрицы (011100) и справа приписывается вторая строка единичной матрицы (0100) и т. д. Причем необходимо отметить, что число элементов в строках производящей и проверочной матриц (n) одно и тоже, а количество строк проверочной матрицы равно числу проверочных элементов производящей матрицы.

a1	a2	a3	a4	a5	а6		b1	b2	b3	b4
H10,6 = 0

После чего для построения кода Хэмминга необходимо преобразовать проверочную матрицу перераспределением ее столбцов таким образом, чтобы кодовая комбинация кортежа столбцов указывала на номер столбца в проверочной матрице H_10,6.

e1	e2		e3				e4
u1	u2	u3	u4	u5	u6	u7	u8	u9	u10
H = 0

Таким образом, проверочная матрица H систематизирована в порядке возрастания номера столбца, причем столбцы u₁, u₂, u₄, u₈ являются столбцами единичной матрицы элементов исходной проверочной матрицы H_10,6.

7. По построенной проверочной матрицы H_10,6 составляются r=4 проверочных уравнений. Проверочные уравнения составляются в виде суммы по модулю 2 элементов строк матрицы H_10,6, элементы единичной матрицы которых равны 1.

e₁ = u₃ Å u₅ Å u₇ Å u₉

(27)

e₂ = u₃ Å u₆ Å u₇ Å u₁₀

e₃ = u₅ Å u₆ Å u₇

e₄ = u₉ Å u₁₀

Полученные уравнения (27) являются исходными (кодообразующими) уравнениями для построения множества кодовых комбинаций кода Хэмминга. В рассмотренном примере на вход формирующего устройства (кодирующего) устройства поступает N_p=60 информационных комбинаций, а на его выходе образуется N_p=60 разрешенных комбинаций кода Хэмминга. Например: на вход кодирующего устройства поступает информационная комбинация 011001. В соответствии с уравнениями (27) u₃=0, u₅=1, u₆=1, u₇=0, u₉=0, u₁₀=1, элементы u₁, u₂, u₄, u₈ являются проверочными элементами e₁, e₂, e₃, e₄, значения которых и необходимо определить по формулам (27).

e₁=u₁=u₃ Å u₅ Å u₇ Å u₉ = 0 Å 1 Å 0 Å 0 = 1

e₂=u₂=u₃ Å u₆ Å u₇ Å u₁₀ = 0 Å 1 Å 0 Å 1 = 0

e₃=u₄=u₅ Å u₆ Å u₇ = 1 Å 1 Å 0 = 0

e₄=u₈=u₉ Å u₁₀ = 0 Å 1 = 1

Таким образом, закодированная по коду Хэмминга разрешенная кодовая комбинация 011001, будет иметь вид:

e1	e2		e3				e4
u1	u2	u3	u4	u5	u6	u7	u8	u9	u10

Исходный код 011001 ® 1000110101 Код Хэмминга

В таблице 4.8 приведен фрагмент кодирования исходных двоичных комбинаций по коду Хэмминга при N_p=60, обнаруживающего и исправляющего одиночные искажения (t=1, S=1).

Таблица 4.8