Кодирование информации (стр. 2 )

а)	а1 Å а3 Å а5 Å а7 = 0	б)	а1 = а3 Å а5 Å а7
	а2 Å а3 Å а6 Å а7 = 0		а2 = а3 Å а6 Å а7	(3.5)
	а4 Å а5 Å а6 Å а7 = 0		а4 = а5 Å а6 Å а7

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

В выбранном 7 элементном блоке 1, 2, 4 разряды заняты под проверочные, а в 3, 5, 6, 7 разрядах запишем передаваемую информацию.

1	0	1		0
а7	а6	а5	а4	а3	а2	а1

Найдем проверочные символы из уравнения (3.5,б)

а1 = а3 Å а5 Å а7 = 0 Å 1 Å1 = 0 а1 = 0

а2 = а3 Å а6 Å а7 = 0 Å 0 Å 1 = 1 а2 = 1

а4 = а5 Å а6 Å а7 = 1 Å 0 Å 1 = 0 а4 = 0

Теперь запишем закодированный блок

1	0	1	0	0	1	0
а7	а6	а5	а4	а3	а2	а1

число 1010010.

Допустим, что при приеме этого блока произошла ошибка в третьем разряде (т. е. мы приняли блок вида 1010110), тогда проверочные равенства (3.5,а) в приемнике дадут синдром ошибки:

а1 Å а3 Å а5 Å а7 = 0 Å 1 Å 1 Å 1 = 1

а2 Å а3 Å а6 Å а7 = 1 Å 1 Å 0 Å 1 = 1

а4 Å а5 Å а6 Å а7 = 0 Å 1 Å 0 Å 1 = 0.

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

3.3.4. Мажоритарное декодирование групповых кодов

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

Пример. Рассмотрим код (7,4), построенный в подразделе 3.3.3. На базе системы проверочных равенств для каждого информационного символа составляем свою систему проверочных равенств (для а7 первые три уравнения получаем из уравнения (3.5,а), четвертое получаем суммирование первых трех уравнений, пятое записываем, исходя из требования нечетного количества уравнений; для а6 первое и второе уравнения получаем из уравнения (3.5,а), третье уравнение получаем из нового первого уравнения путем замены члена а7 первым уравнением из столбца для а7 и сокращением двойных элементов, четвертое уравнение получаем аналогично третьему заменой во втором новом уравнении столбца а6 элемента а7 из первого уравнения столбца а7 и т. д.):

а7 = а1Åа3Åа5;	а6 = а2Åа3Åа7;
а7 = а2Åа3Åа6;	а6 = а3Åа5Åа7;
а7 = а4Åа5Åа6;	а6 = а1Åа2Åа5;
а7 = а1Åа2Åа3;	а6 = а1Åа3Åа4;
а7 = а7;	а6 = а6.

и т. д.

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

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

3.3.5. Групповые коды, исправляющие кратные ошибки

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

Пример. Пусть синдром ошибки в 1-м разряде декодируемой комбинации имеет вид 0001, а в 4-м разряде - 1001. Это означает, что символ а1 входит в 1-е и 4-е равенства, а символ а4 - только в 1-е равенство. Если произойдут ошибки одновременно в 1-м и 4-м разрядах, то равенство, в которое входят символы а1 и а4 останется выполненным, так как

(символ - противоположен символу аi, т. е. если аi=1, то =0 и наоборот). В соответствии со структурой синдромов ни а1, ни а4 во 2-е и
4-е равенства не входят, и следовательно, на их выполнение не влияют. Поэтому при ошибках в 1-м и 4-м разрядах не будет выполняться только
4-е равенство, а значит, синдром такой парной ошибки имеет вид 1000, что соответствует сумме по модулю 2 синдромов в 1-м и 4-м разрядах: 1001Å0001=1000.

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

Для пояснения вернемся к рассмотренному ранее коду (7,4). Предположим, что произошли ошибки в 1-м и 4-м разрядах. Синдром такой двойной ошибки 001 + 011 = 010. Но он уже используется: соответствует ошибке во 2-м разряде, т. е. данный код не исправляет двойных ошибок. Из этого, в частности, следует еще и такой вывод: синдромы одиночных ошибок в информационных разрядах кодов, исправляющих двойные ошибки, должны содержать не менее четырех единиц. В самом деле, допустим, что синдром ошибки в одном из информационных разрядов имеет вид , синдром ошибки в 1-м разряде (проверочном, во 2-м - , в 3-м - . Тогда синдром ошибок в 1-м и 2-м разрядах совпал бы с синдромом ошибок в этом информационном и 3-м разрядах (), что привело бы к невозможности однозначного декодирования. Кроме того, в синдромах ошибок в информационных разрядах единицы должны быть расположены так, чтобы сумма двух синдромов ошибок в информационных разрядах имела не менее трех единиц и не повторялась в виде одинаковых комбинаций.

Литература:

[1] стр. 235-246. [2] стр. 257-282. [3] стр. 131-148.

Контрольные вопросы:

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

2.  Что называется основанием дискретного кода?

3.  Какие коды называются систематическими, а какие - несистематическими?

4.  Дайте определение конечной группы.

5.  Почему некоторые виды корректирующих кодов называют групповыми?

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

7.  Что называется дистанцией Хэмминга в бинарных блочных кодах?

8.  Каким должно быть минимальное расстояние Хэмминга в бинарных блочных кодах?

9.  Каким должно быть минимальное расстояние Хэмминга в коде, исправляющем ошибки кратности К?

10.  Каким должно быть минимальное расстояние Хэмминга в коде, обнаруживающем ошибки кратности К?

11.  Как строится порождающая матрица группового кода?

12.  Какое минимальное количество единиц должны иметь разрешенные комбинации кода, исправляющего одиночные ошибки?

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

14.  Какое количество единиц должны иметь разрешенные комбинации группового кода, обнаруживающего двойные ошибки?

15.  Что называется синдромом ошибки в групповых кодах?

16.  Объясните принцип составления проверочной матрицы группового кода.

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

18.  Источник информации вырабатывает сообщение в виде последовательности букв алфавита с основанием L=15. Для передачи информации по каналу связи используется бинарный код. Какая требуется разрядность блочного корректирующего кода?

19.  Основание кода источника информации L=32. Определите необходимую разрядность безызбыточных комбинаций после перехода на бинарный код.

20.  Задана разрядность безызбыточной комбинации и кратность исправляемых кодом ошибок. Определите необходимое количество разрядов, отводимых под проверочные символы.

21.  Что называется вектором ошибки?

22.  Как соотносятся между собой векторы одиночных и кратных ошибок в групповых кодах?

23.  Сколько единиц должен содержать синдром ошибки в проверочном разряде группового кода?

Задачи:

1.  Записать проверочную матрицу группового кода 7,4, отводя под проверочные символы разряды: а) 1, 2 и 4-й; б) 1, 2 и 3-й, в) 5, 6 и 7-й. Закодировать безызбыточную комбинацию 0001.

2.  Записать проверочную матрицу группового кода, 15,11, отводя под проверочные символы разряды: а) 1, 2, 4 и 8-й; б) 1, 2, 3 и 4-й;
в) 12, 13, 14 и 15-й. Составить порождающую матрицу.

3.  Составить проверочную матрицу группового кода 8,2, отводя под информационные символы разряды: а) 7-й и 8-й; б) 1-й и 2-й; в) 1-й и 5-й. Закодировать безызбыточную комбинацию 11.

4.  Для группового кода 7,4 (задача 1,a) составить систему проверочных равенств для декодирования мажоритарным методом.

5.  Для группового кода 7,4 (задача 1,б) составить систему проверочных равенств для декодирования по синдромам.

6.  Для группового кода 8,2 (задача 3,а) составить систему проверочных равенств для декодирования мажоритарным методом.

3.3.6. Циклические коды

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

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

Ознакомимся с принципами построения циклических кодов на примере кода (7,4). Образуем порождающую матрицу этого кода из комбинаций, содержащих по три единицы. Учтем, что единицы в комбинациях не должны чередоваться с нулями через равные промежутки, так как при суммировании результирующая комбинация по условию замкнутости должна иметь не менее трех единиц. Этим требованиям отвечают только два варианта циклических комбинаций: 0001101 и 0001011. Таким образом, существуют только две матрицы циклического кода (7,4):

Рассмотрим первый вариант циклического кода (7,4). Кодовую комбинацию 0001101 удобно представлять в виде комбинации 1101 с приписанными в старших разрядах тремя нулями. Будем называть комбинацию 1101 порождающей (образующей). Циклический сдвиг кодовой комбинация на один разряд влево можно рассматривать как умножение порождающей комбинации на комбинации 10, 100 и 1000. Полученные таким образом комбинации, естественно, делятся на порождающую без остатка. Не вошедшие в порождающую матрицу разрешенные комбинации можно получить суммированием комбинаций, вошедших в матрицу. Один из возможных вариантов получения всех
15 разрешенных комбинаций сводится к следующему. В качестве 1-й разрешенной комбинации возьмем, например, первую комбинацию из порождающей матрицы: 0001101. Поочередно сдвигая эту комбинацию влево на один разряд, будем иметь еще шесть разрешенных комбинаций. Седьмая комбинация при этом будет такой: 1000110. Просуммировав 1-ю и 2-ю комбинации из порождающей матрицы, получим 8-ю разрешенную комбинацию. Циклическим сдвигом этой комбинации получаем еще шесть разрешенных комбинаций. Наконец. 15-ю комбинацию получаем путем суммирования (по модулю 2) всех комбинаций порождающей матрицы, за исключением 3-й.

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

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

В литературе при рассмотрении теории циклических кодов для удобства кодовые комбинации обычно записываются условно в виде многочленов. С каждой комбинацией сопоставляется соответствующий степенной многочлен, сформированный по следующему правилу: единица в i-м разряде комбинации обозначается как xi-1, отсутствие в многочлене элемента xk-1 означает, что в k-м разряде комбинации стоит нуль. Например, порождающие многочлены рассмотренных вариантов циклического кода (7,4) 1101 и 1011 записываются условно так: х3+х2+1 и х3+х+1, кодовой комбинации эквивалентен многочлен х7.

Построение циклического кода должно начинаться с выбора необходимого порождающего многочлена. В литературе приведены таблицы возможных порождающих многочленов с указанием корректирующих возможностей кодов при использовании этих многочленов. Так, при трех проверочных разрядах порождающие (неприводимые) многочлены имеют два вида: х3+х+1 (1011) и х3+х2+1 (1101); для четырех проверочных разрядов имеется три неприводимых многочлена: х4+х+1 (10011), х4+х3+1 (11001),
х4+х3+х2+х+1 (11111).

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

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

Во втором варианте кодирование сводится к умножению (с суммированием по модулю 2) безызбыточной комбинации на порождающую. Например, при кодировании безызбыточной комбинации 1111 циклическим кодом с порождающей комбинацией 1011 получается следующая комбинация

1111

´ 1011

1111

Å 1111

1111 .

1101001

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

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

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

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

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

Алгоритм первый. Декодируемая комбинация делится на порождающую. Если остаток после деления соответствует синдрому ошибки в младшем разряде, символ исправляется в этом разряде. Если получается иной синдром ошибки, декодируемая комбинация сдвигается на один разряд влево и процедура деления и определения остатка повторяется. Этот цикл (сдвиг - деление) повторяется до тех пор, пока полученный остаток не совпадет с синдромом ошибки в младшем разряде. При совпадении исправляется ошибка в младшем разряде, после чего комбинации сдвигается в обратную сторону в исходное состояние (если было проведено m делений, то производится сдвиг вправо на m-1 разрядов).

Алгоритм второй. Возможность применения этого метода основана на следующем. При делении комбинации с ошибкой на порождающую комбинацию остаток от деления образуется за счет того, что вектор ошибки не делится на порождающую комбинацию. Кроме того, вектор хn+k-1, деленный на порождающий многочлен, дает остаток с единицей в
k-м разряде и нулями в остальных разрядах. Например, в коде (7,4) многочлен х7 (комбинация ) дает остаток 001, многочлен х8 – остаток 010 и т. д. С другой стороны, разрешенная комбинация, сдвинутая влево на любое число разрядов без перестановки старших разрядов (сдвиг при этом сводится к дописанию справа соответствующего количества нулей), также делится на порождающую без остатка. Указанные факторы позволяют применить следующую процедуру исправления ошибок.

1.  Пришедшая комбинация делится на порождающую.

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

3.  Если остаток отличен от нуля, он сравнивается с синдромом, соответствующим ошибке в старшем разряде.

4.  Если при сравнении происходит совпадение, принимается решение о наличии ошибки в старшем разряде и производится исправление.

5.  Если остаток не равен нулю и не совпадает с синдромом ошибки в старшем разряде, к остатку приписывается оправа необходимое количество нулей и деление продолжается. Эта процедура повторяется до тех пор, пока остаток после деления не совпадет с синдромом ошибки в старшем разряде. После выполнения этого условия, если в процессе деления было приписано дополнительно в общей сложности m нулей, исправляется символ в (n-m) - м разряде декодируемой комбинации.

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

Решение. 1. Делим полученную комбинацию на порождающую:

1001000 / 1011

Å 1011

==1000

Å 1011

==110

2. Поскольку синдром ошибки в младшем разряде равен 001, т. е. не совпадает в полученным, сдвигаем полученную комбинацию на 1 разряд влево в снова производим деление:

0010001 / 1011

Å 1011

==111

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

0100010 / 1011

Å 1011

==1110

Å 1011

=101

4. Еще раз повторяем сдвиг и деление:

1000100 / 1011

Å 1011

==1110

Å 1011

=1010

Å 1011

=001

5. Исправляем символ в младшем разряде сдвинутой комбинация:

1000100Å0000001=1000101.

6. Сдвигаем комбинацию в обратном направлении (вправо) на три разряда: 1011000.

7. Отсекаем три младших (проверочных) разряда и передаем потребителю информации комбинацию 1011.

Пример. Используется тот же код, что и в предыдущем примере. Получена комбинация 1001000. Необходимо произвести декодирование по 2-му алгоритму.

Решение. Предварительно в память декодера должен быть заложен синдром ошибки в старшем разряде. Найдем значение этого синдрома как остаток от деления вектора ошибки в 7-м разряде на порождающую комбинацию:

1000000 / 1011

Å 1011

==1100

Å 1011

=1110

Å 1011

=101

Таким образом, синдром ошибки в 7-м разряде равен 101. Делим полученную комбинацию на порождающую:

1001000 / 1011

Å 1011

==1000

Å 1011

==1100 ← дописан

Å 1011

==1100 ← дописан

Å 1011

=101 – синдром ошибки в 7-м разряде

При делении до получения остатка 101 потребовалось дописать два нуля, что эквивалентно сдвигу комбинации на два разряда влево, следовательно, ошибка в принятой комбинации имеет место в 5-м разряде (7-2=5). Суммируя вектор ошибки в 5-м разряде с полученной комбинацией, исправляем:

1001000Å0010000=1011000

3.3.7. Циклические коды, исправляющие кратные ошибки

Циклические коды, исправляющие кратные ошибки, обычно называются кодами БЧХ (от фамилий авторов: Боуз, Чоудхури, Хоквенгем). Хорошие корректирующие свойства и простота построения кодирующих к декодирующих устройств (особенно при необходимости обнаруживать ошибки) обеспечили кодам БЧХ широкое практическое применение. Согласно ГОСТ , основанному на рекомендации МККТТ V×41, в системах передачи данных с решающей обратной связью предписывается использовать циклические коды со следующими параметрами: n=140, 260, 500 и 980, порождающий многочлен х16+х12+х5+1.

Алгоритмы декодирования кодов БЧХ довольно сложны, и их рассмотрение не входит в программу данного курса. В некоторых случаях при небольших длительностях кодовых комбинаций для исправления ошибок может быть применен описанный в подразделе 3.3.6. алгоритм декодирования в более развитом виде. В циклических кодах, исправляющих ошибки до кратности р, при расположении всех ошибок в проверочных разрядах синдром ошибок будет содержать не более р единиц, находящихся в разрядах с ошибками. Это значит, что исправлять ошибки в таком случае можно суммированием остатка с исправляемой комбинацией. Ошибкам в информационных разрядах соответствуют синдром с количеством единиц, большим чем р.

На основании изложенного методика исправления кратных ошибок кодом БЧХ при небольших длинах кодовых комбинаций может сводиться к следующему.

1. Принятая комбинация делится на порождающую.

2. Определяется количество q единиц в остатке:

а) если q≤p, где p - максимальное количество ошибок, исправляемых данным кодом, то ошибок в информационных разрядах нет;

б) если q>p, ошибки есть в информационных разрядах. В этом случае к остатку приписывается необходимое количество нулей, деление продолжается, подсчитывается количество нулей в новом остатке, и при необходимости аналогичная процедура повторяется до получения остатка с количеством единиц p=q.

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

Пример. Применен код БЧХ 15,5, способный исправлять почти все ошибки тройной кратности. Порождающий многочлен кода записывается так: р(х)=х10+х8+х5+х4+х3+х+1, что эквивалентно комбинации . Требуется декодировать принятую комбинацию .

Производим деление:

/

Å

==

Å

==

Å

==

Å

=

Å

=====101001

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

Å 101001

и сдвигаем на три разряда вправо: . Ошибки исправлены. В соответствии с видом синдрома ошибки имели место в 1, 4 и 6-м разрядах сдвинутой комбинации, т. е. в 1, 3 и 13-м разрядах принятой комбинации.

Указанная методика пригодна, например, для кода (15,7), исправляющего одиночные и двойные ошибки. В коде (15,5), исправляющем и тройные ошибки, данная методика позволяет исправлять почти все тройные ошибки (не исправляются тройные ошибки только в случае их расположения в следующих разрядах: ai, ai+5, ai+10, где i≤1¸5).

Литература:

[1] стр. 247-255. [2] стр. 285-289. [3] стр. 149-154.

Контрольные вопросы:

1.  Являются ли циклические коды групповыми?

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

3.  Какими свойствами должен обладать порождающий многочлен циклического кода?

4.  Как проще всего определять синдромы ошибок в циклических кодах.

Задачи:

1.  Записать все разрешенные комбинации циклического кода (7,4) с порождающим многочленом 1011.

2.  Записать все разрешенные комбинации циклического кода (7,4) с порождающей комбинацией 1101.

3.  Задан циклический код (7,4) с порождающей комбинацией 1011. Записать синдромы всех исправляемых кодом ошибок. Декодировать полученную комбинацию 1011111.

4.  Получена комбинация 1 закодированная циклическим кодом (7,4) с порождающей комбинацией 1101. Код используется для обнаружения одиночных и двойных ошибок. Указать возможные варианты ошибок в полученной комбинации.

5.  Используется код БЧХ с порождающим многочленом

х10+х8+х5+х4+х3+х+1

Закодировать комбинацию 11111, ввести в закодированную комбинацию три ошибки и исправить их по указанной методике.

3.3.8. Сверточные коды

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

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

3.3.9. Систематические сверточные коды

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

Рассмотрим простейший сверточный код, известный под названием кода Финка-Хагельбергера и широко применяемый в технике связи. В этих кодах на каждый информационный символ приходится один проверочный (т. е. избыточность составляет 0,5), они способны исправлять как одиночные ошибки, так и пачки ошибок, т. е. несколько ошибок подряд. Исправляются пачки длиной не более h символов при условии, что все соседние пачки разделены промежутком не менее 3h+1, т. е. между последним символом предыдущей пачки и первым символом следующей находится не менее 3h+1 неискаженных символов.

Проиллюстрируем построение и работу кода на конкретном примере. Рассмотрим код, исправляющий пачки ошибок длиной h≤4. Процесс формирования кодовой последовательности показан на рис. 3.2. Кодирование осуществляется следующим образом. По мере поступления на вход кодера информационных символов а формируются проверочные символы b путем суммирования по модулю 2 попарно информационных символов, взятых с интервалом h/2. В более сложных вариантах могут суммироваться не два, а большее число информационных символов.

	0	а1	а2	а3	а4	а5	а6	а7	а8	а9	кодируемая последовательность
	Å	Å	Å	Å	Å	Å	Å	Å	Å	Å
	0	b1	b2	b3	b4	b5	b6	b7	b8	b9	проверочные символы
	0	а1b1	a2b2	a3b3	a4b4	a5b5	a6b6	a7b7	a8b8	a9	сформированная последовательность
№1	0	0	0	1	0	1	0	0	0	0	синдром ошибки в а1
№2	0	0	0	0	1	0	1	0	0	0	синдром ошибки в а2
№3	0	0	0	0	0	1	0	1	0	0	синдром ошибки в а3
№4	0	1	0	0	0	0	0	0	0	0	синдром ошибки в b1
№5	0	0	1	0	0	0	0	0	0	0	синдром ошибки в b2
№6	0	1	0	1	0	1	0	0	0	0	синдром ошибок в а1 и b1
№7	0	1	0	0	1	0	1	0	0	0	синдром ошибок в b1а2
№8	0	1	0	1	1	1	1	0	0	0	синдром ошибок в а1b1а2
№9	0	1	1	0	1	0	1	0	0	0	синдром ошибок в b1а2b2
№10	0	1	1	1	1	1	1	0	0	0	синдром ошибок в а1b1а2 b2
№11	0	1	1	0	1	1	1	1	0	0	синдром ошибок в b1а2b2а3
№12	0	0	0	1	0	1	0	1	0	0	синдром ошибок в а3b3
№13	0	0	0	1	0	1	0	1	0	0	синдром ошибок в а1b7
№14	0	0	0	1	1	1	1	0	0	0	синдром ошибок в а1а2

Рис. 3.2