Учебное пособие по дисциплине СиСПИ

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

К наиболее простым двоичным систематическим кодам относят коды Хэмминга с d=3. Для любого натурального числа r существует код Хэмминга при п=2r—1 и k = n—r. Двойственными кодами к кодам Хэмминга являются эквидистантные коды при n=2r—1, k = r и d = 2r-1 ,причем расстояние между любой парой кодовых комбинаций одинаково, чем и обусловлено название кодов. Коды Хэмминга и эквидистантные обладают свойством равномерно обнаруживать ошибки.

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

1.4.5 Циклические коды

В поисках более простой техники кодирования и декодирования был найден подкласс линейных систематических двоичных кодов, называемых циклическими и применяемых в технике связи. Название этих кодов связано с тем, что каждый вектор, получаемый из кодового циклической перестановкой его символов, также принадлежит коду. Так, например, циклические перестановки вектора 1000101 являются также кодовыми векто-

рами 0001011, 0010110, 0101100 и т. д.

Теория циклических кодов основана на изоморфизме, пространства двоичных n-последовательностей и пространства полиномов степени не выше п—1 вида

60

b(x)			x	x	2	... a		x	n 1	,
	0						n 1
		1	2

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

Легко видеть, что между полиномами и n- последовательностями имеется изоморфизм, причем полиному

соответствует n-последовательность

a	n 1,	a	n 2,	..., a	, a	0	.
				1

Любой полином g(x) степени r<n, который делит без остатка двучлен xn—1, может служить порождающим полиномом циклического (n, k)-кода, где k=n—r. В этот код входят те полиномы, которые без остатка делятся на g(x). В частности, для кода (7,4) порождающим полиномом является

3	.
g(x) 1 x x

(1.54)

Среди циклических кодов особое значение имеет класс кодов, предложенных Боузом и Рой-Чоудхури и независимо от них Хоквингемом. Коды Боуза — Чоудхури — Хоквингема (обозначаемые сокращением БЧХ) отличаются специальным выбором порождающего полинома, вследствие чего для них существуют сравнительно просто реализуемые процедуры декодирования. Доказано, что для любой пары натуральных чисел 5 и t<2s-2 можно построить двоичный код БЧХ с n=2s—1 и k≥n— st, исправляющий любую конфигурацию ошибок с кратностью, меньшей или равной t.

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

61

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

Примером кода, допускающего мажоритарное декодирование, является код, двойственный рассмотренному ранее коду Для него матрица (1.52) является образующей. Ее удобнее записать, переставив столбцы, так:

1		0	0	1	1	1	0
	0	1	0	0	1	1
							1
		0	1	1	1	0
0							1

(1.55)

Символ b1 в этом коде связан с другими символами сле-

дующими соотношениями: b1=b2+b6=b7+b5=b3+b4.									Обозначим
принятые после демодуляции	b1	,	b2	, b3	, b4	, b5	, b6	, b7	. Если бы

они все были приняты верно, то для переданного символа были бы верны следующие четыре равенства (проверки):

b1

b	,
1

b1

b2 b6 , b1

b5

b	,
7

b1 b3	b4	,

(1.56)

Каждый из символов принятого блока входит только в одну из этих проверок для b1. Код, для которого выполняется это условие, называется кодом с разделенными проверками.

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

62

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

волах может получиться одинаковое (верное) значение для b1 во
всех проверках (например, при ошибочно принятых b2		и b6 ) ли-
бо в двух проверках b1	= 0, а в двух других b1=1 (например, при
ошибочно принятых b2	и b1 ). В последнем случае можно только

констатировать наличие ошибок.

После принятия решения о символе b1 аналогично проверяют значения b2 и b3. Поскольку рассматриваемый код (7, 3)— циклический, соответствующие проверки получаются из (1.56) циклической перестановкой.

1.4.6 Сверточные коды

Кодирующее устройство двоичного сверточного кода (рис. 1.16) представляет собой регистр сдвига, состоящий из k ячеек, к выходам которых в определенном порядке подключены п сумматоров по модулю 2. Двоичные информационные символы, поступающие в регистр от источника информации, сдвигаются в регистре на q<k символов, после чего выходы сумматоров по модулю 2 опрашиваются коммутатором и полученная последовательность двоичных символов с выхода коммутатора направляется на модулятор передатчика. Далее этот процесс повторяется. Полученный таким образом код называется сверточным, или рекуррентным кодом. Параметры k, n и q и порядок подключения сумматоров по модулю 2 к ячейкам регистра сдвига определяют структуру получаемого сверточного кода. Избыточность такого кода Rи=1--q/n. Эквивалентная длина сверточного кода равна k.

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

63

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

Рис. 1.16. Кодирующее устройство двоичного сверточного кода.

Рис. 1.17 Кодирующее устройство двоичного сверточного кода при k = 3, n = 2, q=l.

Работу кодирующего устройства сверточного кода удобно пояснить с помощью кодового дерева (рис. 1.18). Кодовое дерево строится следующим образом. Если входной информационный символ, поступающий в сдвигающий регистр, равен 1, то ему приписывается линия (ветвь дерева), идущая, например, вниз, а если информационный символ равен 0- -то вверх. Символы сверточного кода, получаемые на выходе сумматоров по модулю 2, записываются над соответствующей ветвью дерева. Точки, из которых исходят ветви дерева, называются узлами. Определенная последовательность информационных символов

64

на входе кодирующего устройства порождает один из путей по кодовому дереву.

Рис. 1.18. Кодовое дерево, соответствующее кодирующему устройству рис. 1.17.

Например, входная последовательность информационных символов 10001..., поступающая на кодирующее устройство (рис. 1.15), порождает выходную последовательность 1110110011 .... Соответствующий путь по кодовому дереву показан на рис. 1.18 пунктирной линией.

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

65

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

систематическим.

Для декодирования сверточных кодов разработан ряд эффективных методов декодирования, в частности, последовательное декодирование и декодирование А. Витерби .

Принцип последовательного декодирования в двоичном дискретном канале состоит в следующем, п регенерированных символов сверточного кода, соответствующих одной из ветвей кодового дерева, на приемной стороне записывается в регистр сдвига. Декодирующее устройство, аналогичное кодирующему устройству данного сверточного кода, генерирует п символов сверточного кода, соответствующих каждой из ветвей кодового дерева, исходящей из данного узла. Каждая из двух последовательностей п символов, генерируемых в декодирующем устройстве, поразрядно суммируется по модулю 2 с принятой последовательностью, записанной в регистре. В результате этих операций вычисляется расстояние Хэммннга dХ между этими последовательностями и принятой последовательностью. Затем выбирается путь с наименьшим dХ и выносится предварительное решение, что путь по данной ветви кодового дерева и является истинным. Расстояние dХ для этого пути запоминается, и декодирующее устройство переходит к следующему узлу кодового дерева, к которому при водит выбранный путь. Из этого нового узла вновь исследуются два возможных пути п т. д.

Если вероятность искажения одного символа шумами при передаче равна p, то математическое ожидание числа ошибок, а следовательно, и расстояние Хэмминга dХ. между принятыми п символами сверточного кода и п символами, соответствующими правильному пути по данной ветви кодового дерева, будет равно

пр.

66

Если же по данной ветви выбран неправильный путь, то математическое ожидание расстояния dX для него будет приблизительно равно n/2. Следовательно, через l последовательных шагов декодирования математическое ожидание dx(l) для правильного пути будет равно lпр, а для неправильного пути ln/2. Действительные значения dx(l) для правильного п неправильного пути будут случайными величинами с указанными математическими ожиданиями. Это показано на рис. 1.19.

Рис. 1.19. Зависимость кодового расстояния для правильного и неправильного путей.

В последовательном декодирующем устройстве сравнивается текущее значение dx(l) с некоторым порогом z(l) (рис. 1.19). Если на текущем шаге декодирования порог не превышен, то декодирующее устройство переходит к анализу путей, ведущих из следующего узла. Если порог превышен, то декодирующее устройство возвращается в прошлый узел, для которого не было превышения порога, и исследует другие возможные пути по. кодовому дереву. Таким образом, декодирующее устройство обследует все доступные узлы до тех пор, пока не найдется пути, при котором текущий порог z(t) не превышается. Если же

67

такого пути не находится, то порог повышается и указанная операция повторяется.

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

Достоинством последовательного декодирования является то, что при исключении какого-либо пути по кодовому дереву отбрасываются все другие пути, исходящие из узлов исключенного. За счет этого экономится число операций, производимых при декодировании. Чем выше порог z(l), тем большее количество операций требуется, так как неправильный путь, начавшийся из некоторого узла, обнаруживается позднее. Поэтому сначала декодирование ведут при низком (жестком) пороге; при этом пороге декодируется большинство символов сверточного кода. Если же путей, удовлетворяющих этому порогу, не находится (а это случается значительно реже) порог повышают.

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

Рассмотрим теперь принципы декодирования сверточных кодов по методу Витерби. Для этого вновь рассмотрим кодиру-

68

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

На рис. 1.20 четыре возможных состояния первых двух ячеек регистра сдвига кодирующего устройства обозначены цифрами 00, 01, 10, 11, заключенными в рамку. По приходе на кодирующее устройство очередного информационного символа первые две ячейки регистра меняют свои состояния. Если приходящий информационный символ «1», то возможный переход состояния показан пунктирной линией, если «0» — то сплошной линией. Цифрами 1, 2, 3 ... обозначены тактовые моменты прихода на кодирующее устройство информационных символов

Рис. 1.20. Другой вид кодового дерева сверточного кода.

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

69