Материал: 670_Maglitskij_B.N._Otsenka_vlijanija_iskazhenij_i_pomekh_

Рисунок 1.22. – Побайтовое обнаружение и исправление одиночной ошибки в блочном кодере

При наличии одиночной ошибки в этой 8 8 64 - битовой матрице можно указать не только строку, содержащую ошибку, но и столбец с ошибкой, а значит - ошибочный бит, лежащий на пересечении строки и столбца (например, если обнаружена ошибка в 4 – й строке (1 в 8 столбце), 8 – байтовой последовательности, а также в 4 – столбце (1 в 8 строке), то, таким образом, обнаружен ошибочный бит в 4 – й строке 4 – го столбца матрицы).

ВАЖНО! Таким образом, матрица рисунка 4.8 позволяет при ее реализации в виде систематических байтовых кодеров обнаружить и исправить одиночные ошибки.

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

Примером блочного кода, наиболее часто используемого на практике является код Рида – Соломона (RS).

31

Коды Рида-Соломона (Reed-Solomon codes – RS codes) – это широко используемый подкласс недвоичных кодов БХЧ. При использовании кодов Рида - Соломона данные обрабатываются порциями по m бит, именуемыми символами. Код (n, k) характеризуется следующими параметрами:

Таким образом, алгоритм кодирования расширяет блок k символов до размера n, добавляя (n-k) избыточных контрольных символов.

Как правило, m является степенью 2; широко используется значение т = 8.

Рассмотрим пример. Пусть t =1, т = 2. Обозначая символы как 0, 1, 2, 3, их двоичные эквиваленты можно записать как 0 = 00; 1 = 01; 2 = 10; 3 = 11. Код имеет следующие параметры:

n = 22 – 1 = 3 символа = 6 бит, n - k = 2 символа = 4 бит.

С помощью данного кода можно исправить любой пакет ошибок, который искажает 2-битовый символ.

Коды Рида-Соломона удобны для исправления пакетов ошибок. Данный тип кодов характеризуется высокоэффективным использованием избыточности. Длина блоков и размеры символов могут легко приспосабливаться под сообщения разных размеров. Кроме того, для таких кодов существуют эффективные методы декодирования [4].

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

В отличие от блочных кодов, сверточные коды являются непрерывными

(рекуррентными). Их кодирование и декодирование осуществляется непрерывно, без деления информационной последовательности на блоки.

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

32

+

Рисунок 1.23. – Пример схемы сверточного кодера

На рисунке 1.23 изображен сверточный кодер (2,1) с длиной кодового ограничения К=3. В нем имеется n = 2 сумматоров по модулю 2, следовательно, скорость кодирования кода к/n=1/2. При каждом поступлении бит помещается в крайний левый разряд регистра, а записанные биты смещаются на одну позицию вправо. Считывание выходных символов коммутатором К осуществляется после поступления каждого информационного символа, в результате чего формируются пары кодовых символов, образующих кодовое слово, связанное с поступившим битом.

Выбор связи между сумматорами и разрядами регистра влияет на характеристики кода.

Рассмотрим работу кодера при поступлении на его вход информационной последовательности 101. Предположим, что к моменту поступления кодовой последовательности все ячейки регистра находились в состоянии «0» (таблица 1.1)

Таблица 1.1 – Последовательность работы кодера

Ввод в регистр 00

Для очистки регистра после введения трех информационных бит введены (К-1) = 2 нуля. Таким образом, последовательность на выходе кодера выглядит следующим образом: 1110001011. Для удаления сообщения из кодера требуется на 1 меньше нулей, чем число разрядов в регистре, или К-1 очищенных бит.

Отметим, что в рассмотренном примере при входной последовательности из 3 бит и выходной последовательности из 10 бит эффективная степень кодирования составляет к/n = 0,3, что значительно меньше величины 0,5, которую можно было бы ожидать, зная, что каждый бит данных на входе порождает пару канальных битов на выходе. Причина этого заключается в том, что финальные биты данных нужно провести через кодер. Все канальные биты на выходе требуются в процессе декодирования. Если бы сообщение было длинное, например 300 бит и значение степени кодирования 300/640 было бы значительно ближе к 0,5.

Одним из способов представления простых кодирующих устройств является диаграмма состояний. Такое представление кодера приведено на рисунке

1.24.

Рисунок 1.24. – Диаграмма состояний кодера (степень кодирования ½, К=3)

Пути между состояниями – кодовые слова ветвей на выходе, являющиеся результатом переходов между состояниями. Состояния регистра выбраны следующими: а = 00, b = 10, c = 01, d = 11.

34

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

ВАЖНО! Отметим, что за один переход невозможно перейти из данного состояния в любое произвольное. Так как за единицу времени перемещается только один бит, существует только два возможных перехода между состояниями, в которые регистр может переходить за время прохождения каждого бита. Например, если состояние кодера 00, то при следующем смещении возможно возникновения состояний 00 или 10.

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

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

1.25.

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

35