Таблица синдромов ошибок

Принцип синдромного
декодирования рассмотрим на примере
несложного
блокового кода.

Пример 5.3.
Синдромный
декодер систематического кода (7, 4).

В
соответствии с правилом вычисления
синдрома (5.8) для реализации синдромного
декодера необходимо сформировать
транспонированную проверочную матрицу
кода (7, 4). Проверочная матрица этого
кода имеет вид (5.5). Применяя к ней правило
транспонирования матриц, получаем:

,

. (5.9)

Если в канале связи
действуют однократные ошибки, то векторы
ошибок удобно записывать так:

e₁ = (1000000),
e₂ = (0100000),
e₃ = (0010000),
…, e_n = (0000001). (5.10)

В такой
записи вектор ошибки
e_i
представляет набор n
символов, в котором на месте с номером
i (счет
слева) расположен символ ошибки 1, а на
остальных местах расположены нулевые
символы.

векторы
ошибки могут быть представлены в виде
единичной матрицы:

, (5.11)

каждая
строка которой есть вектор
однократной ошибки.
Используя свойства единичных матриц,
нетрудно показать, что матрица синдромов
совпадает с транспонированной проверочной
матрицей этого кода (5.9):

S
= E·H^T
= I_n·H^T
= H^T. (5.12)

При синдромном декодировании блокового кода матрица синдромов S совпадает с транспонированной проверочной матрицей кода HT.

Это
является основанием для составления
таблицы
синдромов.
Ниже приведена табл. 5.1 синдромов для
кода (7,4), составленная по данным строк
транспонированной проверочной матрицы
(5.9). В таблице каждому
вектору ошибки соответствует свой
вектор синдрома,
указывающий местоположение ошибочного
символа в кодовой комбинации на
входе декодера.

таблица 5.1
–Таблица синдромов для декодирования
кода (7, 4)

Синдром	011	110	101	111	100	010	001
Вектор ошибки	e1	e2	e3	e4	e5	e6	e7

Это позволяет
сформулировать алгоритм синдромного
декодирования:

Алгоритм синдромного декодирования блоковых кодов состоит в следующем: 1. Формирование транспонированной проверочной матрицы кода HT. 2. Составление таблицы синдромов для декодирования кода (n, k). 3. Вычисление синдромов (по типу табл. 5.1) по структуре транспонированной проверочной матрицы кода HT и вектору символов декодируемой кодовой комбинации по правилу (5.12). 4. Формирование вектора ошибки ei на основе таблицы синдромов. 5. Исправление ошибки в кодовой комбинации на входе декодера по правилу bi=ei. 6. Отбрасывание дополнительных символов дает комбинацию .

Структура синдромного
декодера кода (7, 4), реализующего этот
алгоритм, приведена на рис. 5.2.

В
соответствии с правилами формирования
синдромов (5.12) на сумматоры по модулю 2
подаются принимаемые из канала символы,
причем, связи с линиями канальных
символов имеются там, где в строках
транспонированной проверочной матрицы
расположен символ 1. В схеме анализатора
синдромов в соответствии с данными
табл. 5.1 происходит преобразование
векторов синдромов S = (s₀,
s₁,
…, s_n–k–1)
в соответствующие им векторы ошибки e,
которые затем подаются на сумматоры
корректора ошибок. В результате сложения
вектора принятых из канала символов
с
соответствующими им векторами ошибки
e
происходит
исправление
канальных ошибок.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

1. /Pomexoustoyxhiviye_kodi_vtelekom_sistemax.doc

Учебное пособие предназначено для бакалавров и магистров, изучающих вопросы помехоустойчивого кодирования, а также для специалистов по защите информации от ошибок

Таблица 2.1

Простой четырех символьный код C(x)	Образующий полином P(x)	Циклический (7,4) код
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	1101	0000000 0001101 0011010 0010111 0110100 0111001 0101110 0100011 1101000 1100101 1110010 1111111 1011100 1010001 1000110 1001011

2.4. Способы исправления ошибок на основе синдрома ошибок, свойства цикличности и анализ веса остатка

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

В циклическом коде для определения синдрома следует разделить приятую кодовую комбинацию на кодовую комбинацию производящего полинома. Если все элементы приняты без ошибок, остаток R(x) от деления равен нулю. Наличие ошибок приводит к тому, что остаток R(x)≠0.

Для определения номеров элементов, в которых произошла ошибка, существует несколько методов. Один из них основан на свойстве, которое заключается в том, что R(х), полученный при делении принятого многочлена H(x) на P_r(x), равен R(x), полученному в результате деления соответствующего многочлена ошибок E(x) на P_r(x).

Многочлен ошибок E(x)=A(x)+H(x) , где A(x)– исходный многочлен циклического кода. Так, если ошибка произошла в а₁, то при коде (9.5) E₁(0,1)=100000000, ошибка в а₂ соответствует E₂(0,1)=010000000 и т.д., остаток от деления E(0,1) на P_r(0,1)=10011=R1(0,1) для данного 9-элементного кода всегда одинаков, он не зависит от вида предаваемой комбинации. В рассматриваемом примере R(0,1)=0101. Наличие ошибки в других элементах (a₂, a₃, …) приведет к другим остаткам. Остатки зависят только от вида P_r(x) и n. Для n=9 и P₄(0,1)=10011 будет следующее соответствие:

Таблица.2.2

Элемент с ошибкой	a1	a2	a3	a4	a5
Синдром	0101	1011	1100	0110	0011

Указанное однозначное соответствие можно использовать для определения места ошибки. Синдром не зависит от переданной кодовой комбинации, но в нем сосредоточена вся информация о наличии ошибок. Обнаружение и исправление ошибок в систематических кодах может производиться только на основе анализа синдрома.

На основании приведенного свойства существует следующий метод определения места ошибки. Сначала определяется остаток R₁(0,1), соответствующий наличию ошибки в старшем разряде. Если ошибка произошла в следующем разряде (более низком), то такой же остаток получится в произведении принятого многочлена и x, т.е. H(x)x. Это служит основанием для следующего приема, суть которого ясна из следующего примера.

Пример: Предположим, задан код (11,7) в виде кодовой комбинации 10110111100. Здесь последние четыре разряда проверочные и получены на основе использования производящего многочлена P(0,1)=100011. Принята кодовая комбинация 10111111100. Определить ошибочно принятый элемент.

Вычисляем R(x) как остаток от деления E(x)=10000000000 на 10011. Произведя деление, получим 0111. Далее делим принятую комбинацию на P_r(x) и получаем остаток R(0,1). Если R(0,1)=R₁(0,1), то ошибка в старшем разряде. Если нет, то дописываем «0» и продолжаем деление. Номер ошибочно принятого разряда (отсчет слева направо) на единицу больше числа приписанных нулей, после которых остаток окажется равным 0111. Проведем процесс деления, отмечая штрихом получаемые остатки R₁(0,1), R₂(0,1), R₃(0,1), R₄(0,1):

(2.6)

В данном примере для этого пришлось дописать четыре нуля. Это означает, что ошибка произошла в пятом элементе, т.е. исправленная кодовая комбинация будет имееть вид

. (2.7)

На основе свойства цикличности, предполагается, что ошибка произошла в старшем разряде. Определяется остаток, соответствующий вектору ошибок:

(2.8)

если остатки совпадают, то ошибка произошла в старшем разряде; если не совпадают, то дописывается 0 в комбинацию R(x) и продолжается деление, пока остатки не совпадут.

Важным свойством циклических кодов является то, что все они строятся с помощью образующего полинома Р(х). приведем методику построения циклического кода. Образующий полином Р(х) принимает участие в образовании каждой кодовой комбинации, поэтому комбинация кода делится на образующий полином без остатка. Однако без остатка делятся только те многочлены (комбинации), которые принадлежат данному коду, т.е. образующий полином позволяет выбрать разрешенные кодовые комбинации из всех возможных. Если же при делении принятой кодовой комбинации циклического кода на образующий многочлен будет получен остаток, значит, имеет место ошибка. Таким образом, остатки от деления принятой комбинации на образующий полином являются опознавателями ошибок циклических кодов. Но данные остатки еще не указывают непосредственно на место ошибки в кодовой комбинации.

В циклических кодах идея исправления ошибок основывается на следующем: ошибочная комбинация после переделанного числа циклических сдвигов «подгоняется» под остаток таким образом, чтобы в сумме с остатком она давала бы исправленную комбинацию. Остаток при этом представляет собой разницу между искаженными и правильными символами, а единицы в остатке стоят на местах искаженных разрядов в «подогнанной» циклическими сдвигами комбинациями. «Подгоняют» искаженную комбинацию до тех пор, пока число единиц в остатке не будет равно числу ошибок в коде. При этом, естественно, число единиц может быть равно числу ошибок tи, исправляемых данным кодом (код исправляет три ошибки и в искаженной комбинации три ошибки) или меньше tи (код исправляет три ошибки, в принятой комбинации – одна ошибка).

Таким образом, для обнаружения и исправления ошибочного разряда производят следующие операции.

1) Принятую комбинацию делят на образующий полином;

2) Подсчитывают количество единиц в остатке (вес остатка). Если

где t_и – допустимое число исправляемых данным кодом ошибок, принятую комбинацию складывают по модулю два с получением остатком. Сумма дает исправленную комбинацию. Если то

3) Производят циклический сдвиг принятой комбинации влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на образующий полином Р(х) . В результате повторного деления делимое суммируют с остатком, затем

4) Производят циклический сдвиг вправо на один разряд комбинации, полученной в результате суммирования последнего делимого с последним остатком. Полученная комбинация уже не содержит ошибок. Если после первого циклического сдвига последующего деления остаток получается таким, что его вес то

5) Повторяют операцию из пункта 3 до тех пор, пока не будет достигнуто

В этом случае комбинацию, полученную в результате последнего циклического сдвига, суммируют с остатком от деления этой комбинации на образующий многочлен, а затем

6) Производят циклический сдвиг вправо ровно на столько разрядов, на сколько сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную комбинацию.

Пример. При передаче комбинации 1001110 циклического кода, исправляющего одиночные ошибки (t_и=1), полученного с помощью образующего полинома произошла ошибка в четвертом разряде. Принятая комбинация имеет вид 1000110. Процесс исправления ошибки следующий:

Делим принятую комбинацию на образующий полином:

(2.9)

2. Сравниваем вес полученного остатка w с числом исправляемых ошибок t_и=1, т. е.

3. Производим циклический сдвиг принятой комбинации на один разряд влево и деление на P(x):

(2.10)

4. Повторяем п. 3 до тех пор, пока небудет получено

(2.11)

5.Складываем по модулю два последнее делимое с последним остатком:

(2.12)

6. Производим циклический сдвиг комбинации, полученный в результате суммирования последнего делимого с последним остатком, вправо на четыре разряда (так как перед этим мы четырежды сдвигали принятую комбинацию влево): Как видим, последняя комбинация соответствует переданной, т.е. не содержит ошибки.

3. Помехоустойчивые коды для коррекции независимых ошибок

В настоящее время среди многих корректирующих кодов широкое применение получили систематические коды особенно их подкласс – циклические коды. Циклическим кодом называется такой код, который вместе с каждым словом а = (a₀,a₁,…, a_n-1,a_n-2) содержит слово ă = (a_n-1, a₀, a₁, …, a_n-2) получающееся из а циклическим сдвигом в право на одну позицию. Характерной особенностью систематических (циклических) кодов является то, что информационные и проверочные разряды кодовой комбинации связанны между собой зависимостями, описываемые линейными уравнениями.

Код Голея занимает уникальное и важное место в теории кодирования. В силу такой хорошей сфере не удивительно, что код Голея тесно связан со многими математическими объектами, и поэтому его можно использовать для перехода от изучения теории кодирования к глубоким задачам теории групп и других областей математики. Дело в том, что код Голея относится к классу совершенных кодов, для которых выполняется следующее условие:

2^k=2ⁿ/(C_n⁰+C_n¹+C_n^t) или 2^k (C_n⁰+C_n¹+…+C_n^t)=2ⁿ , (3.1.)

где n — количество разрядов в кодовой комбинации

k — количество информационных разрядов в кодовой комбинации

Определим код Голея как двоичный циклический код через его порождающий многочлен.

Пусть g(x) и g(x) следующие взаимные многочлены:

g(x)= x¹¹ +х¹⁰+х⁶+х⁵+х⁴+х²+1 (3.2)

g(x)= x¹¹+х⁹+х⁷+х⁶+х⁵+х+1. (3.3)

Простым вычислением проверяется, что

(x-l)g(x)g(x)=x²³-l (3.4)

так что в качестве порождающего многочлена циклического (23,12)-кода можно использовать g(x), так и g(x). Как было сказано выше, минимальное расстояние кода не может быть больше 7. Ниже перечисленные утверждения совместно означают, что минимальный вес кода равен, по меньшей мере, 7.

1. в коде нет слов веса 4 или меньше;

2. в коде нет слов веса 2, 6, 10, 14, 18 и 22;

3. в коде нет слов веса 1, 5, 9, 13. 17 и 21.

Все веса слов в коде Голея исчерпываются числами: 0, 7, 8, 11, 12, 15, 16 и 23. Просчитанное на ЭВМ число слов каждого веса приведено в таблице 3.1.

Для кодирования используются три разновидности кода Голея:

• стандартный код Голея с параметрами (23, 12, 7);

• расширенный — (24, 12, 8);

• укороченный — (18, 6, 8).

Расширенный код Голея (24, 12, образовался добавлением к стандартному одного бита контроля четности. Укороченный код (18, 6, получается путем вычитания левых наибольших шести битов из расширенного кода.

Таблица 3.1.

Веса слов кода Голея

Вес	Число слов
	(23,12)-код	(24,12)-код
0	1	1
7	253	— 759
8	506
11	1288	2576
12	1288
15	506	759
16	253
23	1	0
24	—	1
	4096	4096

Длина вектора ошибок равна 23, а вес не превосходит 3. Длина синдромного регистра равна 11. Если данная конфигурация ошибок не вылавливается, то она не может быть циклически сдвинута так, чтобы все три ошибки появились в 11 младших разрядах. Можно убедиться, что в этом случае по одну сторону от одной из трех ошибочных позиций стоит, по меньшей мере, пять, а по другую сторону — по меньшей мере, шесть нулей. Следовательно, каждая исправляемая конфигурация ошибок может быть с помощью циклических сдвигов приведена к одному из трех следующих видов (позиции нумеруются числами от 0 до 22):

1. все ошибки (не более трех) расположены в 11 старших разрядах;

2. одна ошибка занимает пятую позицию, а остальные расположены в 11 старших разрядах;

одна ошибка занимает шестую позицию, а остальные расположены в 11 старших разрядах. Таким образом, в декодере надо заранее вычислить величины:

S⁵(x)=R_g(x)[xⁿV] и S⁶(x)=R_6(x)[xⁿV] (3.5)

Тогда ошибка вылавливается, если вес S(x) не превышает 3 или вес S(x)-Ss(x) либо S(x)-Se(x) не превышает 2. В декодере можно исправлять все три ошибки, если эти условия выполнены, либо исправлять только две ошибки в младших 11 битах, дожидаясь удаления из регистра третьего ошибочного бита. Разделив х¹⁶ и х¹⁷ на образующий полином g(x)=x¹¹+х¹⁰+х⁶+х⁵+х⁴+х²+1, получаем: S⁵(x)=x⁹+x⁸+x⁶+x⁴+x²+x

(в двоичной форме 01100110110) S⁶(x)=x¹⁰+x⁹+x⁷+x⁶+x³+x²

(в двоичной форме 00110011011)

Следовательно, если ошибка содержится в пятой или шестой позициях, то синдром соответственно равен (01100110110) или (00110011011). Наличие двух дополнительных ошибок в 11 старших разрядах приводит к тому, что в соответствующих позициях два из этих битов заменяются на противоположные.

3.1. Принцип кодирования и декодирования кода Голея

Задачей кодирующего устройства является преобразование k-элементной комбинации (a₀ a₁…a_k-1) исходного без избыточного кода в n-элементную комбинацию (а₀, а₁, a₂, … , a_n-1) избыточного циклического (n,k)-кода. Таким образом, каждая комбинация циклического кода содержит (n-k) избыточных элементов. Под кодированием в широком смысле слова подразумевается представление сообщений в форме, удобной для передачи данных по каналам связи.

Так как код Голея является разновидностью циклических кодов, то к нему применимы следующие методы кодирования:

1-й метод: Деление на образующий полином g(х)

x^r (x) R(x)

———- = Q(x) + ———- (3.6)

g(х) g(х)

Видоизменив уравнение, получим:

Q(x)g(x) = x^r (x) + R(x), (3.7)

где  (х) — кодовая комбинация,

r — степень образующего полинома.

Данный метод кодирования основан на следующем:

1. кодовую комбинацию а=(а₀, a₁, …, а_k-1) сдвигаем па х^r разрядов влево (сдвиг аналогичен умножению на х^r);

2. полученную в результате сдвига комбинацию a=(а_k-1, …, а_n-1), делим на образующий полином g(x);

3. полученный остаток от деления R(x) размещаем на позициях (а₀,, …, а_n-1) кодовой комбинации.

Пример.

Для кодирования комбинации (110101101101), которой соответствует многочлен

(х)= x¹¹ +х¹⁰+х⁸+х⁶+х⁵+х³+ х²+1, умножим сначала на х¹¹ , а затем разделим х^r (х) на образующий полином g(x) и найдем остаток R(x). В результате деления находим, что

R(x)= x¹⁰+х⁹+х⁸+х⁶+х⁵+х⁴+ х³+x² . Кодовый многочлен образуется путем сложения х^г(х) и R(x) согласно (2.2.2).

x^r(х)+R(_Х)=х²²+_Х²¹+_Х¹⁹+х¹⁷+х¹⁶+х¹⁴+х¹³+_Х¹¹+х¹⁰+х⁹+х⁸+х⁶+х⁵+х⁴+х³+х² (3.8)

Этому многочлену соответствует комбинация циклического кода, в которой

110101101101, 11101111100

Информационная часть Проверочная часть

2-й метод: Умножение на образующий полином g(x)

F(x) ≤ p(x)g(x) (3.9)

Данный метод основан на умножении кодовой комбинации (х) на образующий полином g(x). В результате получается комбинация несистематического кода, т.е. комбинация, в которой нельзя определить информационные и проверочные разряды.

Пример.

Необходимо умножить многочлен (x)= x¹¹ +х¹⁰+х⁸+х⁶+х⁵+х³+ х²+1 на g(x)=x¹¹+x⁹+x⁷+x⁶+x⁵+x+1. Умножение осуществляется с использованием сложения по модулю 2. В результате получаем:

(x)g(x)=x²²+x^2l+x²⁰+x¹⁸+x¹⁶+x¹⁵+x¹⁴+x¹³+x¹⁰+x⁸+x⁷+x⁶+x⁴+x²+x+l. (3.10)

Этому многочлену соответствует комбинация циклического кода:

11101011110010111010111.

3-й метод: Использование производящей и проверочной матриц. Этот метод основан на использовании производящей g(x) и проверочной Н(х) матриц.

Как и всякий линейный код, циклический код задается парой матриц: производящей и проверочной. Производящую матрицу можно представить двумя подматрицами: информационной и проверочной. Информационная подматрица имеет k столбцов (т.е. матрица размером kxk), а проверочная — n столбцов. Установлено, что в качестве информационной под матрицы удобно брать единичную матрицу. Количество информационных разрядов k кода Голея равно 12, следовательно, размерность информационной подматрицы Е(х)=2х12. Она имеет вид:

Для построения проверочной подматрицы, которую обозначим как C_r,k, прибегнем к следующему способу: выбираем комбинацию Q(x), содержащую только одну единицу, и делим ее на образующий полином g(x) с получением остатка R(x), который в результате и есть строка проверочной подматрицы.

Допустим, единичный вектор равен 00000000000100000000000, тогда первая строка подматрицы С₁(х) получается следующим образом:

C₁(x)=R(x)= 01011100011 (3.11)

Аналогичным образом, сдвигая каждый раз единицу в следующий разряд информационной комбинации, получаем последующие строки проверочной подматрицы С(х).

Данную операцию проводим i=1k раз.

Таким образом, проверочная подматрица имеет вид:

Полученная подматрица С_11,12 приписывается справа к единичной подматрице E_{12, 12} в результате чего получается производящая матрица G_{23, 12}.

Теперь, для кодирования любой комбинации (х) достаточно выбрать из нее разряды, равные 1, и сложить по модулю 2 соответствующие номерам выбранных разрядов строки матрицы G_23,12

В циклических кодах, а именно в кодах Голея, процесс кодирования сводится к определению r проверочных разрядов. Каждый проверочный разряд определяется с помощью проверочного соотношения, а определение r проверочных разрядов требует r проверочных соотношений, которые записываются одно под другим в виде проверочной матрицы Н_n,r

Проверочная матрица Н может быть построена с помощью проверочного полинома:

h(x)=(xⁿ+l)/g^-1(x), (3.12)

где g^-1 (x) — полином, сопряженный с образующим полиномом или обратный ему.

h(х)=(х²³+1)/(х¹¹+х⁹+х⁷+х⁶+х⁵+х+1)^-1 = х¹²+х¹¹+х¹⁰+х⁹+х⁸+х⁵+х²+1 (3.13)

что в двоичной форме: 1111100100101.

Последующие строки проверочной матрицы Н получаются с помощью циклического сдвига полученной комбинации, проверочного полинома.

В результате проверочная матрица имеет вид:

Также проверочную матрицу в каноническом виде можно получить из производящей матрицы. Образование этой матрицы производится путем замены строк производящей матрицы на столбцы.

Процесс образования схематично показан стрелками на рис. 3.1.

рис. 3.1 Схема образования проверочной матрицы Н

G_23,12— производящая матрица

E_12,12— информационная подматрица

H_23,11 — проверочная матрица

В результате проверочная матрица имеет вид:

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

Пример.

С помощью проверочной матрицы Н определим проверочные символы при комбинации:

(110101101101).

Для вычисления первого проверочного разряда берем первую строку проверочной матрицы:

B₁=а₂ а₅ а₈ а₉ а₁₀ а₁₁ a₁₂= 1001101=0

B₂=а₁₁ а₄ а₇ а₈ а₉ а₁₀ а₁₁=1110110=1

B₃=а₂ а₃ а₅ а₆ а₇ а₁₁ а₁₂=1001101=0

B₄=а₁ а₂ а₄ а₅ а₆ а₁₀ а₁₁=1110110=1

B₅=а_] а₂ а₃ а₄ а₈ а₁₁ а₁₂=1101001=0

B₆⁼а₁а₃ а₅ а₇ а₈ а₉ а₁₂=1001011=0

B₇=а₄ а₅ а₆ а₇ а₉ а₁₀ а₁₂=1011111=0

B₈=а₃ а₄ а₅ а₆ а₈ а₉ а₁₁=0101010=1

B₉=а₂ а₃ а₄ а₅ а₇ а₈ а₁₀ = 1010101=0

B₁₀=а₁₁ а₂ а₃ а₄ а₆ а₇ а₉ = 1101111=0

B₁₁=а₁а₃ а₆ а₉ а₁₀ а₁₁ а₁₂=1011101=1

Таким образом, комбинация линейного кода имеет вид:

(11010110110101010001001).

Задачей декодера является обратное преобразование принятой поэлементной комбинации циклического кода в исходную k-элементную комбинацию. При этом эффективность циклического кода оценивается его способностью корректировать возникающие при передаче по каналу ошибки.

Декодирование кода Голея можно производить двумя методами:

• декодером Меггита;

• на основе алгоритма Берлекмпа-Месси (в данном случае код Голея рассматривается как разновидность БЧХ).

Декодером Меггита можно однозначно определить и исправить трехкратные ошибки, а алгоритм Берлекемпа-Месси исправляет только двухкратные ошибки. Также необходимо учесть простоту и сравнительную дешевизну аппаратного исполнения декодера Меггита по сравнению с декодером БЧХ. Поэтому в настоящее время в качестве декодера кода Голея используется декодер Меггита.

Принцип работы декодера Меггита основан на «вылавливании» ошибок, расположенных в старших разрядах. При этом должно выполняться следующее условие: длина информационной части не должна превышать длины синдромов ошибок.

Декодер Меггита проверяет синдромы только для тех конфигураций ошибок, которые расположены в старших разрядах. Декодирование ошибок в остальных позициях основано на циклической структуре кода и осуществляется позднее. Соответственно таблица синдромов содержит только те синдромы, которые соответствуют многочленам ошибок с ненулевым коэффициентом e_n_i. Если вычисленный синдром находится в этой таблице, то e_n_i исправляется. Затем принятое слово циклически сдвигается и повторяется процесс нахождения возможной ошибки в предшествующей по старшинству позиции (e_n-i *0). Этот процесс повторяется последовательно для каждой компоненты; каждая компонента проверяется на наличие ошибки, и если ошибка найдена, то она исправляется.

Опишем декодер Меггита для (23,12)-кода Голея.

Длина вектора ошибок равна 23, а вес не превосходит 3. Длина синдромного регистра равна 11. Если данная конфигурация ошибок не вылавливается, то она не может быть циклически сдвинута так, чтобы все три ошибки появились в 11 младших разрядах. Можно убедиться, что в этом случае по одну сторону от одной из трех ошибочных позиций стоит, по меньшей мере, пять, а по другую сторону — по меньшей мере, шесть нулей. Следовательно, каждая исправляемая конфигурация ошибок может быть с помощью циклических сдвигов приведена к одному из трех следующих видов (позиции нумеруются числами от 0 до 22):

1. все ошибки (не более трех) расположены в 11 старших разрядах;

2. одна ошибка занимает пятую позицию, а остальные расположены в 11 старших разрядах;

3. одна ошибка занимает шестую позицию, а остальные расположены в 11 старших разрядах. Таким образом, в декодере надо заранее вычислить величины:

S⁵(x)=R_g(x)[xⁿV] и S⁶(x)=R_6(x)[xⁿV]. (3.14)

Тогда ошибка вылавливается, если вес S(x) не превышает 3 или вес S(x)-Ss(x) либо S(x)-Se(x) не превышает 2. В декодере можно исправлять все три ошибки, если эти условия выполнены, либо исправлять только две ошибки в младших 11 битах, дожидаясь удаления из регистра третьего ошибочного бита.

Разделив х¹⁶ и х¹⁷ на образующий полином

g(x)=x¹¹+х¹⁰+х⁶+х⁵+х⁴+х²+1, получаем S⁵(x)=x⁹+x⁸+x⁶+x⁴+x²+x (в двоичной форме 01100110110), S⁶(x)=x¹⁰+x⁹+x⁷+x⁶+x³+x² (в двоичной форме 00110011011). Следовательно, если ошибка содержится в пятой или шестой позициях, то синдром соответственно равен (01100110110) или (00110011011). Наличие двух дополнительных ошибок в 11 старших разрядах приводит к тому, что в соответствующих позициях два из этих битов заменяются на противоположные.

Декодер отслеживает синдром, отличающийся от нулевого синдрома не более чем в трех позициях, а также синдром, отличающийся от выписанных двух синдромов не более чем в двух позициях.

Пример.

Допустим, что передавалось кодовое слово

С(х)= 10101010101001100001011.

При передаче часть символов исказилась: V(x)=C(x)+e(x). Многочлен ошибок равен: е(х)=00100000001000000010. Тогда принимаемое слово: V(x)==lo8oi010100001100001o5l, где искаженные символы обозначены значком (*). Определяем синдром S(x)=10011000111.

Рассмотрим второй этап декодирования (где r⁶(x)=x’⁶mod g(x)=00110011011, г (х)=х mod g(x)=01100110110). В каждом цикле шаги а,б,в,г -вычисления. На 17 цикле вес Wa=2 и осуществляется исправление ошибок суммированием по модулю 2 содержимого буферного устройства (старшие разряды) с синдромом и 6 символ заменяется на обратный. В это время искаженные два символа находятся в старших разрядах n-разрядах буферного устройства, а третий — в 6 разряде буфера.

Операция вычисления очередного синдрома выполняется следующим образом: анализируется старший разряд синдрома, и если он равен единице, то производится сдвиг содержимого синдрома на 1 разряд влево и суммирование по модулю 2 с образующим полиномом g(x), в противном случае осуществляется только сдвиг синдрома влево.

3.2. Принцип построения кода БЧХ

Одним из наилучших среди известных неслучайных кодов, для которых предложены удобные алгоритмы кодирования и декодирования являются коды БЧХ (Боуза-Чоудхури-Хеквингема). Коды БЧХ представляют собой большой класс циклических кодов, исправляющих независимые ошибки кратности t и менее. Для кодов БЧХ характерны все основные свойства циклических кодов.

Свойство 1. Циклический код в полиномиальном его представление можно определить как множество многочленов степени n-1 и меньше, каждый из которых делится без остатка на некоторый многочлен P(x), называемый образующим или порождающим многочленом кода.

Свойство 2. Если кодовая комбинация а_i, a₃,…, a_n—i, a_n принадлежит циклическому коду, то и комбинация, полученная из предыдущей в результате циклического сдвига её элементов, например (а_n, a₁, a₂, …, a_n-1, a_n, … a_n-2), также принадлежит этому циклическому коду.

Коды БЧХ определяются величинами n, k, d, g(x),

где: n — количество элементов в кодовой комбинации,

k – количество информационных элементов кода БЧХ,

d – количества проверочных разрядов кода БЧХ,

g(x) – порождающий многочлен кода БЧХ.

Построение кодов предложенных Боузом-Чоудхури основано на следующем. Мультипликативная группа поля Галуа GF(2^m) содержит n=2^m-1 элементов и является циклической группой {a} порядка 2^m-1(здесь а – примитивный элемент поля Галуа). Но каждый элемент конечной группы в степени, равной порядку группы, равен единице (т.е. a^m = 1). Поэтому все 2^m-1 ненулевые элементы поля GF(2^m) являются корнями многочлена 1-(2^m-1)-1. Порождающий многочлен циклического кода длинной n=2^m-1 должен без остатка делить многочлен х=2^m-1, следовательно, корни многочлена g(x) должны содержаться. Например, для кода n = 2^m-1=15 производящий многочлен является делителем многочлена z = 2^m-1, т.е.

x^15-1 = g₁(x) g₂(x) g₃(x) g₄(x)(x-1) (3.15)

Здесь под неправильным делителем g(x) выписаны их корни, т.к. среди корней g₁(x) и g₄(x) содержаться две последовательные степени а, то, что они могут быть выбраны в качестве порождающих многочленов с d₀ ≥ = 3. g₁(x) и g₄(x) имеют соответственно вид:

g₁(x)=x⁴+x²+x+1 (3.16)

g₄(x)=x⁴+x³+ x²+x+1 (3.17)

т.к. deg g₁(x)=4 (т.е. максимальная степень g₁(x)), то длина информационных разрядов равна n-k=4, отсюда k=n-4=15-4=11 получаем код БЧХ (15,11) способный исправить однократную ошибку. Для получения большего n—k=4 необходимо взять в качестве производящего многочлена произведение g₂(x) и g₄(x), содержащие четыре последовательные степени a: a¹¹, a¹², a¹³, a¹⁴.

deg (g₂(x), g₄(x))=8 отсюда n—k=8 и k=15-8=7. Получаем код БЧХ (15,7) с d_0≥5, который может исправлять 2-х кратные ошибки.

Примитивные двоичные коды БЧХ, таким образом, строятся для любого числа n=2^m-1 и любого t=2^m-1, определяется кодовое расстояние d₀>=2t+1, число проверочных символов должно быть равно или меньше mt, число информационных символов k=n-deg(g(x)).

3.3. Принцип кодирования и декодирования кода БЧХ

Параметры кода БЧХ выбираются следующим образом:

1) Выбирается число n, исходя из формулы n=2^m—1, где m – любое целое число.

2) Определяется количество ошибок, которые необходимо исправить

(3.18)

отсюда код БЧХ должен иметь вид d₀>2t+1.

3) В зависимости от величины d₀ вычисляется

g(x)=НОКm₁(x),…m_2t(x),

где m₁(x) … m_2t(x) – минимальные неприводимые многочлены (т.е. m₁(x) = g₁(x))

4) Число проверочных символов вычисляется по формуле: r = m · t.

5) Количество информационных символов k вычисляется по формуле

K = n – r = (2^m – 1) – r (3.19)

Существует несколько способов кодирования кода БЧХ:

1) Любой циклический код задается порождающим многочленом.

Отношение (3.20) называется проверочным многочленом.

(3.20)

Поскольку g(x) и h(x) однозначно определяют друг друга, код БЧХ может быть задан порождающей и проверочными матрицами.

Для циклического кода (n,k) с порождающим многочленом g(x) можно найти k линейно независимых кодовых комбинаций образующих порождающую матрицу |G|.

В неканоническом виде |G’| имеет вид.

После преобразования эта матрица приводится к канонической форме |G|:

|G| = |J_k·A_k2|,

где J_k – единичная матрица размерности k x k,

A_k2 – матрица коэффициентов уравнений проверок, связывающих значений информационных и проверочных разрядов.

Для того, что бы закодировать простую комбинацию, необходимо умножить эту комбинацию на матрицу |G|, т.е. сложить по mod 2 строки порождающей матрицы |G| номера, которых соответствуют ненулевым элементам простого кода.

Полученный код является несистематическим, т.е. код, в котором нельзя разделить информационные разряды от проверочных.

Построить систематический код можно с помощью проверочной матрицы |H|. Проверочная матрица имеет вид:

|H| = |B^t, I_n-1| (3.21)

где B^t – значение матрицы проверочных соотношений размерностью k x k

I_n-1 – единичная матрица размерностью (n — k) x k.

2) Другой способ кодирования кода БЧХ состоит в следующем:

Необходимую кодовую комбинацию a(x) = a₀….a_k-1 сдвигаем на x_n-k разрядов влево. Получим число

X^n-k a(x) = X^n-k(a₀=…=a_k-1 X^k-1)=a₀ X^n-1+…+ a_k-1 X^n-1 (3.22)

Разделим теперь многочлен X^n-k a(x) на g(x) и запишем делимое в виде

X^n-k a(x) = g(x)q(x) + r(x) (3.23)

где q(x) – частное,

r(x) – остаток от деления на g(x).

Так как степень многочлена g(x) = n – k, то степень r(x) = n – k – 1.

Тогда:

X^n-k a(x) + r(x) = g(x)q(x) (3.24)

Отсюда получаем искомую кодовую комбинацию разделимого кода БЧХ.

Отличие кодов БЧХ от других циклических кодов состоит в том, что согласно определению коды БЧХ работают с неприводимыми многочленами в поле GF(q), которые могут иметь корни в некотором расширении.

Если q является степенью числа (q = q^m), то элементами поля являются все многочлены степени m-1, коэффициенты которых лежат в простом поле GF(р). Поля, которые являются расширением в простом поле GF(q), называются полем Галуа. Элемент поля GF(q^m)представляет собой m разрядный вектор с q элементами.

Алгоритм декодирования БЧХ состоит из нескольких этапов:

1) Вычисление синдрома.

2) Вычисление многочлена локатора ошибок.

3) Нахождение корней многочлена локатора ошибок.

4) Исправление ошибок.

Рассмотрим каждый этап.

1) Вычисление синдрома при декодировании можно выполнить двумя способами: с помощью проверочной матрицы H^т или по формуле (3.25)

S_j = 2^n-1 ea^2(m+j) (3.25)

где е — ошибки, а – элементы поля Галуа

Рассмотрим оба способа.

1.1 С помощью проверочной матрицы Н. Использование проверочной матрицы H^т основано на факте:

G· H^т =0, (3.26)

где G –каноническая матрица, H^т — транспонированная контрольная матрица. Поэтому если принятое слово принадлежит кодовому множеству, т.е. в нем отсутствуют ошибки, то

Х· H^т =0 (3.27)

1.2 Второй способ основан на вычислении синдромов по (i₁, i₂, … ,i_v).

(3.28)

где v – количество ошибок по позициям (i₁, i₂, … ,i_v);

а – элементы поля Галуа.

Для двоичных кодов БЧХ синдромы четных определяются как квадраты предыдущих нечетных синдромов, т.е. S₂ = S₁² и т.д. Если же все синдромы равны S₁ – S_q, то ошибок нет.

2) Зная значения синдромов, необходимо определить многочлен локаторов ошибок Л|Z|, т.к.

(3.29)

то, решив её можно определить место расположения ошибок. Данная система уравнений называется ключевыми уравнениями. Известны два наиболее удачных алгоритма вычисления ключевого уравнения Питерсона и Берлекампа – Месси.

Для многочлена локаторов ошибок Л|Z| необходимо определить последовательность минимальной длины L, чтобы посредством уравнений

(3.30)

она порождала известную последовательность S₁, S₂ … S_2t синдрома. Величина L должна быть минимальной, потому что она равна числу
ошибок, но так как ошибки в канале независимы и равновероятны, то
наиболее вероятным вектором — ошибкой должен быть вектор
минимального веса, ибо этот вес есть кратность ошибки.

Основная черта алгоритма Берлекампа — Месси состоит в следующем: вначале находим самый короткий регистр сдвига L, порождающий с S₁ по S₀. Далее проверяем, порождает ли этот регистр также S₂. Если порождает, то этот регистр по-прежнему остается наилучшим решением, и нужно продолжать проверять, порождает он следующие символы синдрома. На каком-то шаге очередной символ уже не будет порождаться, в этот момент нужно изменить регистр таким образом, чтобы он:

а) правильна, предсказал следующий символ S;

б) не менял предсказаний предыдущих символов;

в) увеличивал длину на максимально возможную величину.

Этот процесс нужно продолжать до тех пор, пока не будут
порождены первые 2t символа синдрома.

3. Определение локаторов ошибок и, следовательно, корней многочлена локаторов ошибок можно выполнить с помощью процедуры Ченя. Согласно процедуре Ченя, корнем ключевого уравнения должен быть элемент поля Галуа, удовлетворяющий условию (3.31)

Л(а^-1) = 0, (3.31)

где i-ошибочный символ. Отсюда:

.

Таким образом, для обнаружения местоположения ошибок необходимо перебрать все элементы поля Галуа GF (2ⁿ) и, если n(а^-1) = 0, то обратный элемент а¹ и будет являться локатором ошибок и укажет место положения ошибки.

4. Зная место положения, ошибок, производят исправление ошибок согласно формуле:

С^(х) = r(х) + с(х),

где с^ (х) — исправленная кодовая комбинация,

r(х) — принятая кодовая комбинация,

с(х) — вычисленные местоположения ошибок.

Пример реализации кода БЧХ.

В этом примере рассматривается декодирова­ние циклического (7,4,3) кода Хемминга с порождающим мно­гочленом g(x) = х³+х+1. Схема вычисления синдрома показана на Рисунке 3.2. Принимаемые символы накапливаются в реги­стре сдвига и одновременно вводятся в схему деления на g(x). После приема седьмого бита содержимое этого регистра сдви­гается на один разряд в каждом такте, а схема деления модифи­цирует синдром и проверяет совпадение с полиномом х⁶ mod(l+х+х³)= 1+х² ↔ 101 (в двоичной записи).

Рис.3.2. Синдромный декодер двоичного циклического (7,4,3) кода Хэмминга.

Как только на выходе схемы проверки появится 1, будет исправ­лена ошибка в позиции х⁶. В тот же самый момент исправление вводится по обратной связи в схему деления и, тем самым, обну­ляет остаток от деления. Нулевой остаток может рассматривать­ся как сигнал об успешном завершении декодирования. Провер­ка на нулевой остаток схемы деления позволяет обнаруживать некоторые аномалии по окончании процедуры декодирования. Перейдем теперь к изучению циклических кодов, исправ­ляющих многократные ошибки, для которых задача декодиро­вания может рассматриваться как решение системы уравне­ний. По этой причине здесь необходимо знакомство с полем, в котором будут выполняться операции умножения, сложения и деления. Циклические коды имеют хорошую алгебраичес­кую структуру. Позднее будет показано, что эффективная реа­лизация мощных алгоритмов декодирования достигается при использовании арифметики конечного поля, когда известно размещение корней порождающего многочлена кода.

Напомним, что порождающий полином всегда может быть представлен произведением двоичных неприводимых много­членов:

Алгебраическая структура циклических кодов выражается, в частности, в возможности определения корней каждого из многочленов в некотором поле разложения (которое явля­ется расширением поля, которому принадлежат коэффициен­ты многочлена). В интересующем нас случае поле разложения неприводимого многочлена является полем Галуа. В литерату­ре поля Галуа называют также конечными полями, имея в виду конечное число принадлежащих ему элементов. Стандартным обозначением является

Принципы помехоустойчивого кодирования

Помехоустойчивым (корректирующим) кодированием называется кодирование при котором осуществляется обнаружение либо обнаружение и исправление ошибок в принятых кодовых комбинациях.

Возможность помехоустойчивого кодирования осуществляется на основании теоремы, сформулированной Шенноном, согласно ей:

если производительность источника (Hи’(A)) меньше пропускной способности канала связи (Ск), то существует по крайней мере одна процедура кодирования и декодирования при которой вероятность ошибочного декодирования сколь угодно мала, если же производительность источника больше пропускной способности канала, то такой процедуры не существует.

Основным принципом помехоустойчивого кодирования является использование избыточных кодов, причем если для кодирования сообщения используется простой код, то в него специально вводят избыточность. Необходимость избыточности объясняется тем, что в простых кодах все кодовые комбинации являются разрешенными, поэтому при ошибке в любом из разрядов приведет к появлению другой разрешенной комбинации, и обнаружить ошибку будет не возможно. В избыточных кодах для передачи сообщений используется лишь часть кодовых комбинаций (разрешенные комбинации). Прием запрещенной кодовой комбинации означает ошибку. Причем, в процессе приема закодированного сообщения возможны три случая (рисунок 3).

Прием сообщения без ошибок является оптимальным, но возможен только если канал связи идеальный. В этом случае помехоустойчивое декодирование не нужно.

В реальном канале из-за воздействия помех происходят ошибки в принимаемых кодовых комбинациях. Если принимаемая кодовая комбинация в результате воздействия помех перешла (трансформировалась) из одной разрешенной комбинации в другую, то определить ошибку не возможно, даже при использовании помехоустойчивого кодирования.

Если же передаваемая разрешенная кодовая комбинация, в результате воздействия помех, трансформируется в запрещенную комбинация, то в этом случае существует возможность обнаружить ошибку и исправить ее.

Помехоустойчивое кодирование может осуществляться двумя способами: с обнаружением ошибок либо с исправлением ошибок. Возможность кода обнаруживать или исправлять ошибки определяется кодовым расстоянием.

Если осуществляется кодирование с обнаружением ошибок, то кодовое расстояние должно быть хотя бы на единицу больше чем кратность обнаруживаемых ошибок, т. е.

d₀? q_{о ош} + 1.

Если данное условие не выполняется, то одни из ошибок обнаруживаются, а другие нет.

Если осуществляется кодирование с исправлением ошибок, то кодовое расстояние должно быть хотя бы на единицу больше удвоенного значения кратности исправляемых ошибок, т. е.

d₀? 2q_{и ош} + 1.

Если данное условие не выполняется, то одни из ошибок исправляются, а другие нет.

Следует отметить, что если код способен исправить одну ошибку (q_{и ош} = 1), что соответствует кодовому расстоянию 3 (d₀ = 1?2+1 = 3), то обнаружить он может две ошибки, т. к.

q_{о ош} = d₀ – 1 = 2.

Декодирование помехоустойчивых кодов

Декодирование — это процесс перехода от вторичного отображения сообщения к первичному алфавиту.

Декодирование помехоустойчивых кодов может осуществляться тремя способами: сравнения, синдромным и мажоритарным.

Способ сравнения основан на том, что, принятая кодовая комбинация сравнивается со всеми разрешенными комбинациями, которые заранее известны на приеме. Если принятая комбинация не совпадает ни с одной из разрешенных, выносится решение о принятии запрещенной комбинации. Недостатком данного способа является громоздкость и необходимость большого времени для декодирования в случае применения многоразрядных кодов. Данный способ используется в кодах с обнаружением ошибок.

Синдромный способ  основан на вычислении определенным образом контрольного числа — синдрома ошибки (С). Если синдром ошибки равен нулю, то кодовая комбинация принята верно, если синдром не равен нулю, то комбинация принята не верно. Данный способ может быть использован в кодах с исправлением ошибок, в этом случае синдром указывает не только на наличие ошибки в кодовой комбинации, но и на место положение этой ошибки в кодовой комбинации. Для двоичного кода знание местоположения ошибки достаточно для ее исправления. Это объясняется тем, что любой символ кодовой комбинации может принимать всего два значения и если символ ошибочный, то его необходимо инвертировать. Следовательно, синдрома ошибки достаточно для исправления ошибок, если d₀? 2q_{и ош} + 1.

Мажоритарное декодирование основано на том, что каждый информационный символ кодовой комбинации определяется нескольким линейными выражениями через другие символы кодовой комбинации. Если принята комбинация без ошибок, то все соотношения остаются и все выражения дают одинаковые результаты (единицу или ноль). При ошибке в одном из разрядов эти соотношения нарушаются, в результате чего одни линейные выражения равны нулю, а другие единице. Решение о принятом символе определяется по большинству: если в результате вычислений выражений больше нулей, то принимается решение о принятии нуля, если больше единиц, то принимается решение о приеме единицы. Если, при декодировании, результаты вычисления выражений дают одинаковое число единиц и нулей, то при определении принятого символа приоритет имеет принятый символ, значение которого в данный момент определяется.

Классификация корректирующих кодов

Классификация корректирующих кодов представлена схемой (рисунок 4)

Блочные — это коды, в которых передаваемое сообщение разбивается на блоки и каждому блоку соответствует своя кодовая комбинация (например, в телеграфии каждой букве соответствует своя кодовая комбинация).

Непрерывные — коды, в которых сообщение не разбивается на блоки, а проверочные символы располагаются между информационными.

Неразделимые — это коды, в кодовых комбинациях которых нельзя выделить проверочные разряды.

Разделимые — это коды, в кодовых комбинациях которых можно указать положение проверочных разрядов, т. е. кодовые комбинации можно разделить на информационную и проверочную части.

Систематические (линейные) — это коды, в которых проверочные символы определяются как линейные комбинации информационных символов, в таких кодах суммирование по модулю два двух разрешенных кодовых комбинаций также дает разрешенную комбинацию. В несистематических кодах эти условия не выполняются.

Код с постоянным весом

Данный код относится к классу блочных не разделимых кодов. В нем все разрешенные кодовые комбинации имеют одинаковый вес. Примером кода с постоянным весом является Международный телеграфный код МТК-3. В этом коде все разрешенные кодовые комбинации имеют вес равный трем, разрядность же комбинаций n=7. Таким образом, из 128 комбинаций (N₀ = 2⁷ = 128) разрешенными являются Nа = 35 (именно столько комбинаций из всех имеют W=3). При декодировании кодовых комбинаций осуществляется вычисление веса кодовой комбинации и если W?3, то выносится решение об ошибке. Например, из принятых комбинаций 0110010, 1010010, 1000111 ошибочной является третья, т. к. W=4. Данный код способен обнаруживать все ошибки нечетной кратности и часть ошибок четной кратности. Не обнаруживаются только ошибки смещения, при которых вес комбинации не изменяется, например, передавалась комбинация 1001001, а принята 1010001 (вес комбинации не изменился W=3). Код МТК-3 способен только обнаруживать ошибки и не способен их исправлять. При обнаружении ошибки кодовая комбинация не используется для дальнейшей обработки, а на передающую сторону отправляется запрос о повторной передаче данной комбинации. Поэтому данный код используется в системах передачи информации с обратной связью.

Код с четным числом единиц

Данный код относится к классу блочных, разделимых, систематических кодов. В нем все разрешенные кодовые комбинации имеют четное число единиц. Это достигается введением в кодовую комбинацию одного проверочного символа, который равен единице если количество единиц в информационной комбинации нечетное и нулю ? если четное. Например:

При декодировании осуществляется поразрядное суммирование по модулю два всех элементов принятой кодовой комбинации и если результат равен единице, то принята комбинация с ошибкой, если результат равен нулю принята разрешенная комбинация. Например:

101101 = 1 + 0 + 1 + 1 + 0 + 1 = 0 — разрешенная комбинация

101111 = 1 + 0 + 1 + 1 + 1 + 1 = 1 — запрещенная комбинация.

Данный код способен обнаруживать как однократные ошибки, так и любые ошибки нечетной кратности, но не способен их исправлять. Данный код также используется в системах передачи информации с обратной связью.

Код Хэмминга

Код Хэмминга относится к классу блочных, разделимых, систематических кодов. Кодовое расстояние данного кода d₀=3 или d₀=4.

Блочные систематические коды характеризуются разрядностью кодовой комбинации n и количеством информационных разрядов в этой комбинации k остальные разряды являются проверочными (r):

r = n — k.

Данные коды обозначаются как (n,k).

Рассмотрим код Хэмминга (7,4). В данном коде каждая комбинация имеет 7 разрядов, из которых 4 являются информационными,

При кодировании формируется кодовая комбинация вида:

а₁ а₂ а₃ а₄ b₁ b₂ b

где а_i — информационные символы;

b_i — проверочные символы.

В данном коде проверочные элементы b_i находятся через линейные комбинации информационных символов a_i, причем, для каждого проверочного символа определяется свое правило. Для определения правил запишем таблицу синдромов кода (С) (таблица 3), в которой записываются все возможные синдромы, причем, синдромы имеющие в своем составе одну единицу соответствуют ошибкам в проверочных символах:

• синдром 100 соответствует ошибке в проверочном символе b₁;
• синдром 010 соответствует ошибке в проверочном символе b₂;
• синдром 001 соответствует ошибке в проверочном символе b₃.

Синдромы с числом единиц больше 2 соответствуют ошибкам в информационных символах. Синдромы для различных элементов кодовой комбинации а_i и b_i должны быть различными.

Таблица 3 — Синдромы кода Хэмминга (7;4)

Число	Элементы синдрома	Элементы кодовой
синдрома	С1	С2	С3	комбинации
1	0	0	1	b3
2	0	1	0	b2
3	0	1	1	a1
4	1	0	0	b1
5	1	0	1	a2
6	1	1	0	a3
7	1	1	1	a4

Определим правило формирования элемента b₃. Как следует из таблицы, ошибке в данном символе соответствует единица в младшем разряде синдрома С4. Поэтому, из таблицы, необходимо отобрать те элементы а_i у которых, при возникновении ошибки, появляется единица в младшем разряде. Наличие единиц в младшем разряде, кроме b₃,соответствует элементам a₁, a₂ и a₄. Просуммировав эти информационные элементы получим правило формирования проверочного символа:

b₃ = a₁ +    a₂  +  a₄

Аналогично определяем правила для b₂ и b₁:

b₂ = a₁ +  a₃ + a₄

b₁ = a₂ +  a₃ + a₄

Пример 3, необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем b_i:

b₁ = 1 +  0 + 1 = 0; b₂ = 1 + 0 + 1=1; b₃ = 1 + 1 + 1 = 1.

Добавляем проверочные символы к информационным и получаем кодовую комбинацию:

Biр = 1101001.

В теории циклических кодов все преобразования кодовых комбинаций производятся в виде математических операций над полиномами (степенными функциями). Поэтому двоичные комбинации преобразуют в полиномы согласно выражения:

Аi(х) = а_n-1x^n-1 + а_n-2x^n-2 +…+ а₀x⁰

где a_n-1, … коэффициенты полинома принимающие значения 0 или 1. Например, комбинации 1001011 соответствует полином

Аi(х) = 1?x⁶ + 0?x⁵ + 0?x⁴ + 1?x³ + 0?x² + 1?x+1?x⁰ ? x⁶ + x³ + x+1.

При формировании кодовых комбинаций над полиномами производят операции сложения, вычитания, умножения и деления. Операции умножения и деления производят по арифметическим правилам, сложение заменяется суммированием по модулю два, а вычитание заменяется суммированием.

Разрешенные кодовые комбинации циклических кодов обладают тем свойством, что все они делятся без остатка на образующий или порождающий полином G(х). Порождающий полином вычисляется с применением ЭВМ. В приложении приведена таблица синдромов.

Этапы формирования разрешенной кодовой комбинации разделимого циклического кода Biр(х).

1.  Информационная кодовая комбинация Ai преобразуется из двоичной формы в полиномиальную (Ai(x)).

2.  Полином Ai(x) умножается на х^r,

Ai(x)?x^r

где r количество проверочных разрядов:

r = n — k.

3.  Вычисляется остаток от деления R(x) полученного произведения на порождающий полином:

R(x) = Ai(x)?x^r/G(x).

4.  Остаток от деления (проверочные разряды) прибавляется к информационным разрядам:

Biр(x) = Ai(x)?x^r + R(x).

5.  Кодовая комбинация Bip(x) преобразуется из полиномиальной формы в двоичную (Bip).

Пример 4. Необходимо сформировать кодовую комбинацию циклического кода (7,4) с порождающим полиномом G(x)=х³+х+1, соответствующую информационной комбинации 0110.

1. Преобразуем комбинацию в полиномиальную форму:

Ai = 0110 ? х² + х = Ai(x).

2. Находим количество проверочных символов и умножаем  полученный полином на x^r:

r = n – k = 7 – 4 =3

Ai(x)?x^r = (х² + х)? x³ = х⁵ + х⁴

3. Определяем остаток от деления Ai(x)?x^r на порождающий полином, деление осуществляется до тех пор пока наивысшая степень делимого не станет меньше наивысшей степени делителя:

R(x) = Ai(x)?x^r/G(x)

4. Прибавляем остаток от деления к информационным разрядам и переводим в двоичную систему счисления:

Biр(x) = Ai(x)?x^r+ R(x) = х⁵ + х⁴ + 1? 0110001.

5. Преобразуем кодовую комбинацию из полиномиальной формы в двоичную:

Biр(x) = х⁵ + х⁴ + 1 ? 0110001 = Biр

Как видно из комбинации четыре старших разряда соответствуют информационной комбинации, а три младших — проверочные.

Формирование разрешенной кодовой комбинации неразделимого циклического кода.

Формирование данных комбинаций осуществляется умножением информационной комбинации на порождающий полином:

Biр(x) = Ai(x)?G(x).

Причем умножение можно производить в двоичной форме.

Пример 5, необходимо сформировать кодовую комбинацию неразделимого циклического кода используя данные примера 2, т. е. G(x) = х³+х+1, Ai(x) = 0110, код (7,4).

1. Переводим комбинацию из двоичной формы в полиномиальную:

Ai = 0110? х²+х = Ai(x)

2. Осуществляем деление Ai(x)?G(x)

3. Переводим кодовую комбинацию из полиномиальной форы в двоичную:

Bip(x) = х⁵+х⁴+х³+х ? 0111010 = Bip

В этой комбинации невозможно выделить информационную и проверочную части.

Матричное представление систематических кодов

Систематические коды, рассмотренные выше (код Хэмминга и разделимый циклический код) удобно представить в виде матриц. Рассмотрим, как это осуществляется.

Поскольку систематические коды обладают тем свойством, что сумма двух разрешенных комбинаций по модулю два дают также разрешенную комбинацию, то для формирования комбинаций таких кодов используют производящую матрицу G_n,k. С помощью производящей матрицы можно получить любую кодовую комбинацию кода путем суммирования по модулю два строк матрицы в различных комбинациях. Для получения данной матрицы в нее заносятся исходные комбинации, которые полностью определяют систематический код. Исходные комбинации определяются исходя из условий:

1)      все исходные комбинации должны быть различны;

2)      нулевая комбинация не должна входить в число исходных комбинаций;

3)      каждая исходная комбинация должна иметь вес не менее кодового расстояния, т. е. W?d₀;

4)      между любыми двумя исходными комбинациями расстояние Хэмминга должно быть не меньше кодового расстояния, т. е. d_ij?d₀.

Производящая матрица имеет вид:

Производящая подматрица имеет k строк и n столбцов. Она образована двумя подматрицами: информационной (включает элементы а_ij) и проверочной (включает элементы b_ij). Информационная матрица имеет размеры k?k, а проверочная — r?k.

В качестве информационной подматрицы удобно брать единичную матрицу E_kk:

Проверочная подматрица G_r,k строится путем подбора различных r-разрядных комбинаций, удовлетворяющих следующим правилам:

1)      в каждой строке подматрицы количество единиц должно быть не менее d₀-1;

2)      сумма по модулю два двух любых строк должна иметь не менее d₀-2 единицы;

Полученная таким образом подматрица G_r,k приписывается справа к подматрице E_kk, в результате чего получается производящая матрица G_n,k. Затем, используя производящую матрицу, можно получить любую комбинацию кода путем суммирования двух и более строк по модулю два в различных комбинациях.

Пример 6. Необходимо построить производящую матрицу кода Хэмминга способного исправлять 1 ошибку и имеющего n=7. Закодировать с помощью полученной матрицы комбинацию Ai=1101.

Определяем кодовое расстояние:

d₀=2q_{и ош}+1= 2?1+1=3.

Для кодов с d₀=3 количество проверочных разрядов определяется по формуле:

r=log₂(n+1)= log₂8=3.

Определяем разрядность информационной части:

k = n — r = 7 — 4 =3.

Запишем все возможные комбинации проверочной подматрицы: 000, 001, 010, 011, 100, 101, 110, 111. Выберем из этих комбинаций те, что удовлетворяют правилам:

1)      в каждой строке не менее d₀-1, этому условию соответствуют комбинации 011, 101, 110, 111;

2)      сумма двух любых комбинаций по модулю два содержит единиц не менее d₀-2:

3)      записываем проверочную подматрицу:

4)      приписываем полученную подматрицу к единичной и получаем производящую матрицу:

Если произвести определение d₀ для исходных комбинаций полученной матрицы (определив расстояние Хэмминга для всех пар комбинаций), то оно окажется равным 3.

Для кодирования заданной комбинации Ai, необходимо просуммировать те строки матрицы G, которые в информационной части имеют единицу на том месте, на котором они находятся в комбинации Аi. Для заданной комбинации 1101 единичными разрядами являются а₁, а₂, а₄. В матрице G единицы на этих местах имеют строки: первая, вторая и четвертая. Просуммировав их получаем разрешенную комбинацию заданного кода.

Сравнивая полученную кодовую комбинацию Bip с комбинацией полученной примере 3, для которой также использована комбинация Ai=1101, видим что они одинаковы.

Для кода Хэмминга выше были определены правила формирования проверочных символов b_k:

Эти правила можно отобразить в виде проверочной матрицы Н_n,k. Она состоит из n столбцов (соответствует разрядности кодовой комбинации) и r столбцов (соответствует количеству проверочных разрядов кодовой комбинации). В правой части матрицы указываются синдромы, соответствующие ошибкам в проверочных символах, в левой части записываются элементы информационной части комбинации, причем, те элементы, которые участвуют в образовании определенного элемента b_i равны единицы, а те которые не участвуют — нулю.

В данном случае обведенные пунктиром проверочные элементы образуют единичную матрицу. Проверочная матрица позволяет определить ошибочный разряд, поскольку каждый столбец данной матрицы представляет собой синдром соответствующего символа. При этом строки матрицы будут соответствовать разрядам синдрома C_k. Например, согласно приведенной проверочной матрице, синдром соответствующий ошибку в разряде а₁ имеет вид 011, в разряде а₂ — 101, в разряде а₃ — 110, в разряде а₄ — 111, в разряде b₁ — 100, в разряде b₂ — 010, в разряде b₃ — 001. Также с помощью проверочной матрицы легко определить проверочные и символы и сформировать кодовую комбинацию. Например, необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем b_i:

b₁ = 1 + 0 + 1 = 0; b₂ = 1 + 0 + 1=0; b₃ = 1 + 1 + 1 = 1.

Добавляем проверочные символы к информационным и получаем кодовую комбинацию:

Biр = 1101001.

Также проверочную матрицу можно построить и другим способом. Для этого сначала строится единичная матрица Е_r. К которой слева приписывается подматрица D_k,r. Каждая строка этой подматрицы соответствует столбцу проверочных разрядов подматрицы С_r,k производящей матрицы G_n,k.

Такое преобразование строк матрицы в столбцы называется транспонированием.

В результате получаем

Декодирование циклических кодов

При декодировании таких кодов (разделимых и неразделимых) используется Синдромный способ. Вычисление синдрома осуществляется в три этапа:

1. принятая комбинация Bip’ преобразуется их двоичной формы в полиномиальную (Bip(x));

2. осуществляется деление Bip(x) на порождающий полином G(x) в результате чего определяется синдром ошибки C(x) (остаток от деления);

3. синдром ошибки преобразуется из полиномиальной формы в двоичную;

4. По проверочной матрице или таблице синдромов определяется ошибочный разряд;

5. Ошибочный разряд в Bip’(x) инвертируется;

6. Исправленная комбинация преобразуется из полиномиальной формы в двоичную Bip.

делением принятой кодовой комбинации Biр’(x) на порождающий полином G(x), который заранее известен на приеме. Остаток от деления и является синдромом ошибки С(х).

Мажоритарное декодирование циклических кодов

Мажоритарное декодирование может применятся только для декодирования систематических кодов (кода Хэмминга, циклического разделимого кода). Рассмотрим мажоритарное декодирование на примере циклического кода.