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

Если не выполня­ется проверка на четность для i-й строки и j-го столбца то эле­мент, стоящий на пересечении i-й строки и j-го столбца заменя­ется на обратный. При использовании в качестве итерируемых кодов систематических кодов к итеративному коду также приме­ним матричный способ описания. Можно показать, что порождающая матрица итеративного кода, использующего два сис­тематических кода с порождающими матрицами G_A и G_B, равна G = G_AG_B, где G_AG_B есть векторное произведение порождающих матриц. Так, если, например,

Такая матрица позволяет сформировать код n=9, k=4, d₀=4.

Даже простейший итеративный код обладает высокими обнару­живающими способностями. При действии пакетов ошибок об­наруживается любой пакет ошибок длиной l+1 и менее, где l - длина строки.

Существенным недостатком итеративных кодов, использую­щих проверки на четность, является их избыточность, составляю­щая обычно 15 -20% и значительно превышающая избыточность эквивалентных по свойствам циклических кодов. Однако при ис­пользовании программных методов кодирования и декодирования с помощью ЭВМ проще работать с итеративными кодами. Поэто­му на практике они широко используются в системах передачи данных.

Лекция 8 Принципы построения кодирующих устройств Код с поэлементным формированием проверочной группы

1. Шифратор

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

Проверочные элементы записываются в остальные r ячеек (r=4), где они формируются по ранее определенному правилу, т. е. в соответ­ствии с условными номерами информационных элементов, состав­ляющих проверочные группы. Эти правила для кода Хемминга (9,5) рассмотрены ранее и имеют вид:

(*)

Так, в ячейку 6 регистра следует за­писать проверочный элемент b₄. Значение этого элемента (0 или 1) определяется суммированием по модулю 2 информацион­ных элементов a₁, a₂, a₄, a₅ и т. д.

2. Декодер

В приемном устройстве решаются следующие задачи:

• преобразование последовательного n-элементного кода в параллельный и запись кодовых комбинаций в ячейки параллельного регистра;

• анализ принятых кодовых комбинаций с целью выявления ошибки и определения ее места;

• исправление обнаруженной ошибки;

• преобразование исправленной информационной группы элемен­тов в последовательный k-элементный код.

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

а) Обнаружение ошибки

Структурная схема декодера кода (9,5) приведена на рисунке. С ячеек девятиразрядного запоминающего регистра элементы кодовой комбинации поступают в устройство анализа, в качестве которого ис­пользуются сумматоры по модулю 2. На каждый из r сумматоров (число сумматоров равно числу проверочных элементов кодовой комбинации, т.е. в примере их 4) поступают соответствующий принятый проверочный элемент b'_i (разряды регистра 6 – 9) и та совокупность информационных элементов, которая определя­ет его значение в соответствии с требованиями проверок (см. выражения (*)). Так, на сумматор № 1 поступает принятый проверочный элемент b'₄, а также информационные элементы а₁, а₂, а₄, а₅. На сумматор № 2 поступает принятый проверочный элемент b'₃, и информационные элементы а₁, а₃, а₄ и т.д.

Результаты суммирования (0 либо 1) записываются в ячейки r-разрядного параллельного регистра, выполняющего функции индикатора ошибок. На вы­ходе индикатора ошибок может появиться одно из 2^r-1 двоичных чисел, определяющих условный номер ошибочно принятого элемента. В данном примере таких чисел может быть только 9, т.к. кодовая комбинация имеет только 9 элементов.

На практике отмечаются только ошибки, возникшие в информационной части кодовой комбинации. Для рассматриваемого случая (k=5) в индикаторе ошибок может быть записано только шесть двоич­ных чисел: 0000, 0011, 0101, 0110, 0111, 1001. Первое число указывает на отсутствие ошибок. Второе число указывают на на­личие ошибки в первом элементе информационной части (условный номер элемента а₃). Третье – на ошибку во втором элементе информационной части (условный номер элемента а₅) и т.д. Т.о. двоичные числа определяют условный номер элемента, который использовался при составлении уравнений (*) при нахождении проверочных элементов кодовой комбинации.

Автоматическое определение номера элемента, в котором об­наружена ошибка, производится с помощью цифровых фильтров, настроенных на числа 0011, 0101, 0110, 0111, 1001. На выходе со­ответствующего фильтра сигнал возникает лишь в случае, когда в индикаторе ошибки записано двоичное число, соответ­ствующее данному фильтру. Принцип построения таких фильтров ясен из схемы, где функции фильтра выполняет схема совпаде­ния (схема И) на четыре входа.

Предположим, что ошибка произошла в стар­шем разряде информационной части кодовой комбинации (элемент с условным обозначением а₃). В этом случае в индикаторе ошибок будет сформировано число 3 (0011). Чтобы это число дало отклик на выходе соответствующей схемы И (на рисунке – 5 разряд), необходимо обеспечить формирование единиц на всех ее четырех входах. Для этого с третьей и четвертой ячеек индикатора ошибок (ячейки b₁, b₂) следует подавать сигнал через инверторы (схема «НЕ»). Любое другое число, сформиро­ванное в регистре индикатора ошибок, не будет соответствовать настройке этой схемы И и отклика на ее выходе не даст.

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

Процесс исправления ошибки сводится к изменению ошибочно принятого элемента кодовой комбинации. Это происходит в устройстве для исправления ошибок, которое представляет собой регистр сдвига, обеспечивающий наряду с ис­правлением ошибки преобразование параллельного кода в после­довательный. Изменение ошибочно принятого информационного элемента осуществляется его суммированием по модулю 2 с еди­ницей, формируемой на выходе схемы И устройства обнаружения ошибок, соответствую­щей данному элементу. Если ошибки нет, то на выходе схемы И будет нуль, при наличии ошибки — единица. В случае, когда ошибки нет (независимо от того нуль или единица представляют данный информационный элемент), суммирование элемента с нулем результата не изменит, т.к. 1 0=1; 0 0=0. Наличие ошибки изменит элемент на противоположный, т. е. 1 1=0; 0 1=1.

Суммирование по модулю 2 реализуется схемой совпадения (схема И), на входы которой соответственно поступают элемент информационной комбинации и напряжение, снимаемое с выхода схемы И устройства обнаружения ошибок после инвертирования схемой НЕ. Этот принцип иллюстрируется рисунком ниже. Буквой U_i обозначен элемент информационной комбинации i-го разряда, буквой П_i – элемент на выходе схемы И_i устройства обнаружения ошибок, которая контролирует U_i. Исправленные элементы поступают в ячейки регистра сдвига. Регистр сдвига устройства исправления ошибок содержит одну дополнительную ячейку. После записи в ячейки 1-5 регистра исправленные элементы продвигаются тактовыми импульсами. После первого тактового импульса на выход регистра поступит элемент 5-го разряда, затем 4-го и т.д.