Остатки Векторы ошибок Остатки

на n -м такте

Детектор для выделенного синдрома 100 можно построить из одного логического элемента НЕ и одного элемента ИЛИ — НЕ.

На рис. 6.20 представлена схема декодирующего устройства для этого случая.

Табл. 6.18 позволяет проследить по тактам процесс исправления ошибки в кодовой комбинации 1000011 (искажен символ в 4-м разряде).

Таблица 6.18

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

Пример 6.19. Рассмотрим более сложный случай исправления одиночных и двойных смежных ошибок. Для этой цели может использоваться циклический код (7,3) с образующим многочленом g(x) = (x+1)(x³ + x²+1).

Ориентируясь на схему деления за k тактов, найдем выделенный синдром для двойных смежных ошибок:

Остатки Остатки Векторы ошибок на n-м такте

Для одиночных ошибок соответственно получим

Остатки Векторы ошибок на n -м такте

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

Процесс исправления кодовой комбинации 1000010 с искаженными символами в 4-м и 5-м разрядах поясняется табл. 6.19.

На 9-м такте в схеме деления II появляется первый выделенный синдром 1100. На следующем такте на выходе аналогично обозначенного элемента ИЛИ — НЕ детектора ошибок формируется импульс коррекции, который исправляет 5-й разряд кодовой комбинации и одновременно по цепи обратной связи изменяет остаток в схеме деления II, приводя его в соответствие выделенному синдрому еще неисправленной одиночной ошибки в 4-м разряде (1000) На 11 м такте импульс коррекции формирует элемент ИЛИ — НЕ детектора ошибок, соответствующий указанному выделенному синдрому. Этим импульсом обеспечивается исправление 4-го разряда кодовой комбинации и получение нулевого остатка в схеме деления II

Таблица 6.19

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

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

В качестве примера рассмотрим класс кодов Файра с образующим многочленом

где р(х) — неприводимый многочлен степени m>=Ь, принадлежащий показателю степени е = 2^m-1; b — длина корректируемого пакета ошибок.

Поступающую из канала связи кодовую комбинацию h(x) представляем суммой по модулю два неискаженной комбинации кода f(x) и вектора, соответствующего пачке ошибок В(х):

где х1 характеризует положение пачки ошибок В(х) в векторе ошибки. Вектор f(x) делится на каждый из многочленов g1(x) и g2(x) без остатка Поэтому процесс декодирования можно анализировать, ограничиваясь вектором х^i*В(х). Отметим, что при выбранном нами соотношении числа разрядов в пакете ошибок и степени образующего многочлена m = b совокупность различных исправляемых пакетов ошибок является одновременно совокупностью остатков, получаемых при делении на р(х). В качестве остатка на n-м такте (выделенного синдрома) при пакете ошибок в старших разрядах h(x) желательно иметь сам многочлен ошибки. Тогда на следующих тактах, выводя его в узел коррекции синхронно с последовательностью h(x) из буферного регистра, легко исправить искаженные символы.

Остаток на n-м такте мы получим только в том случае, если будем использовать схему, обеспечивающую деление с первого такта и требующую домножения h(x) на х^m.

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

При поступлении h(x) в схему деления I [на многочлен р(х)] в ней начинается закономерное чередование остатков В(х), являющийся одним из остатков, появляется в первый раз на (2^m-1)-м такте. Следовательно, для того чтобы он появился на n-м такте, общее число разрядов должно быть кратно 2^m-1.

В процессе деления h(x) на многочлен х^2b-1 + 1, принадлежащий показателю (2b — 1), образуется (2b — 1) остатков. Вектор типа В(х)х^b-1 является одним из остатков. Он возникает впервые на (2b — 1)-м такте и затем его появление циклически повторяется с периодом (2b — 1) тактов

Если мы желаем выставить этот остаток в детекторе ошибки, т. е. получить его также на n-м такте, то n должно быть кратно (2b—1). Чтобы детектор ошибки не сработал раньше, числа 2^m-1 и 2b — 1 должны быть взаимно простыми, а n — наименьшим кратным этих чисел.

Равенство остатков В(х) в регистрах двух схем деления, а также равенство нулю остальных (b — 1) разрядов в схеме деления II (на многочлен х^b2 + 1) являются условиями возможности исправления обнаруженного пакета ошибок и устанавливаются схемным путем.

После фиксации условий, допускающих исправление пакета, ключ Κι замыкается, а ключ K2 размыкается. На схему коррекции (сумматор по модулю два) одновременно начинают выводиться символы В(х) как с буферного регистра, так и со схемы деления II. При этом пакет ошибок В(х) в векторе h(x) устраняется.

В общем случае, когда В(х) начинается не со старшего разряда, а с j-го, для обеспечения равенства остатков, полученных на n-м такте, нужно проводить последовательные домножения их на x с приведением по модулю р(х) в одной схеме и по модулю (x^2b-1 + 1) — в другой.

Если пачка начинается с j-го разряда, то необходимо сделать дополнительно (n-j) тактов, прежде чем остатки в регистрах сравняются, причем с учетом домножения h(x) на х^m*j может принимать значения от 1 до n.

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

Если за время вывода h(x) из буферного регистра условия возможности проведения коррекции не были выполнены, то обнаружена неисправимая ошибка.

Пример 6.20. Рассмотреть процесс исправления пакетов ошибок кодом Файра с образующим многочленом

Код может исправлять пакеты ошибок, состоящие из трех символов (b = 3). Длина кодовой комбинации равна n = (2³—1)(2 ·3^-1) = 35. Предположим, что в трех старших разрядах нулевой кодовой комбинации возникла пачка ошибок типа В(х) = 101.

При делении В(х) на g1(x) = х³ + x²+ 1 остаток В(х) будет появляться в регистре с периодом 7 тактов. Действительно,

Чередование остатков В(х)х^b-1 при делении В(х) на g2(x) = x⁵ + 1 происходит с периодом 5 тактов.

Последовательность изменения остатков в регистрах схем деления I и II при поступлении на вход декодирующего устройства нулевой кодовой комбинации с пачкой ошибок 101 в старших разрядах приведена в табл. 6.20. В силу специфики работы схемы деления за k тактов первые b — 1 остатков отличаются от полученных при делении столбиков.

Таблица 6.20

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

Мажоритарное декодирование циклических кодов. Система контрольных проверок, найденная для одного (например а_i) или нескольких символов кодовой комбинации циклического кода, может быть использована для декодирования всех символов этой кодовой комбинации, так как контрольным соотношениям удовлетворяет любая кодовая комбинация, а следовательно, и комбинация, полученная из принятой циклическим сдвигом. Таким образом, для декодирования символа а_i+k достаточно произвести k сдвигов и осуществить решение «по большинству» посредством того же мажоритарного элемента.

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

Приведем контрольные равенства в развернутом виде:

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

1. каждое контрольное равенство позволяет выразить некоторый символ а, посредством линейной комбинации символов, которые не входят ни в какое другое равенство (система разделенных проверок);

2. систему разделенных проверок удается построить только относительно суммы каких-либо символов (система квазиразделенных проверок);

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

Последнюю систему называют λ-связанной, если хотя бы один символ a_i(i неравно j) входит в λ равенств и никакой другой a_j (i неравно j) в большее число равенств не входит. Поскольку способы выражения символов а_iоказываются зависимыми, общее число нетривиальных проверок, требующееся для исправления и обнаружения ошибок, по сравнению с предыдущим случаем должно быть больше [16].

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

Ограничимся рассмотрением конкретного примера только для этого случая.

Пример 6.21. Составим систему разделенных проверок и построим схему декодирующего устройства для циклического кода (7,3) с образующим многочленом g(x) = (x+1)(x³ + x + 1), предназначенного для исправления единичных и одновременного обнаружения двойных ошибок (d = 4)

Найдем генераторный многочлен

Выражая символ старшего разряда a0 через различные символы и добавляя тривиальную проверку a₀ = а₀, получим систему:

Запишем контрольные равенства:

Соответствующая схема декодирующего устройства представлена на рис. 6.23.

Поступившая в буферный регистр кодовая комбинация параллельно переписывается в регистр декодера. На каждом из n последующих тактов на входе мажоритарного элемента M формируются сигналы в соответствии с равенствами (6.47).

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

Табл. 6.21 позволяет проследить процесс мажоритарного декодирования для случая, когда одиночная ошибка произошла в 4-м разряде кодовой комбинации 1001110.

Таблица 6.21

Случай, когда на двух входах мажоритарного элемента оказывается сигнал «1», а на двух других — «0», соответствует обнаружению двойной ошибки.

§ 6.9. КОДЫ БОУЗА — ЧОУДХУРИ — ХОКВИНГЕМА

Математическое введение. Рассматриваемые циклические коды, сокращенно называемые БЧХ - кодами, составляют большой класс кодов, предназначенных для исправления независимых ошибок произвольной кратности s. Их минимальное кодовое расстояние, следовательно, должно быть не менее чем d_min = 2s + 1.

Для понимания математической структуры БЧХ - кодов необходимо ознакомиться с некоторыми новыми понятиями линейной алгебры. В общем случае эти понятия справедливы для множества многочленов с коэффициентами из поля GF(q), где q — простое число. Поскольку нас интересуют в первую очередь двоичные коды, мы ограничимся случаем q = 2.

Ранее было рассмотрено разложение кольца на классы вычетов по идеалу (см. табл. 6.10). Если в качестве образующего многочлена идеала g(x) взят неприводимый многочлен степени т, принадлежащий показателю степени n(n = 2^m—1), то общее число классов вычетов, включая идеал, равно 2^m.

Зададим операции сложения и умножения для полученных классов вычетов:

где (ri(х)) — класс вычетов по модулю многочлена g(x) содержащий элемент ri(x).

При этом совокупность классов вычетов образует конечное поле. Оно насчитывает 2^m элементов, обозначается GF(2^m) и называется расширением поля степени m над GF(2). Единичным и нулевым элементами поля являются классы вычетов соответственно (1) и (0).

Нетрудно убедиться в том, что для любого ненулевого элемента поля (г_a(х)) в нем найдется обратный ему элемент (r_a(х)), удовлетворяющий равенству

Пример 6.22. Построим поле порядка 24, используя неприводимый многочлен g(x) = x⁴ + x + 1 ·

Полная совокупность классов вычетов равна числу остатков, получающихся при делении произвольного многочлена на многочлен р(х). Для заданного многочлена эта совокупность составляет 16 классов вычетов: (0), (1), (x), (х+1), (х²), (х²+1), (х²+х), (х²+х+1), (х³), (х³+1), (х³+х), (х³+х²), (х³+х+1), (х³+х²+1), (х³+х²+х), (х³+х²+х+1).

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

Таблица 6.22

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

Доказано, что в любом конечном поле найдется по крайней мере один элемент α, такой, что все ненулевые элементы поля могут быть представлены в виде различных степеней αⁱ этого элемента, называемого примитивным элементом поля. Так как рассматриваемое поле конечно и насчитывает n=2^m-1 ненулевых элементов, то начиная с αⁿ = 1 элементы поля начнут повторяться.

Элементы поля могут быть выражены и через отрицательные степени α, так как поле содержит мультипликативный обратный элемент каждого ненулевого элемента. Используя элементы α^m-1, α^m-2,..., α, 1 в качестве базиса, элементы поля можно представить также в виде двоичных последовательностей (векторное представление).

Пример 6.23. Приведем различное представление элементов поля, построенного на основе неприводимого многочлена g(x) = х⁴ + х+1 (табл. 6.23).

Таблица 6.23

Выражение элементов через отрицательную степень α осуществляется делением на α¹⁵ = 1.

Покажем теперь, что любой элемент конечного поля порядка 2^m является корнем уравнения

Для ненулевых элементов поля соответственно имеем

Если α — примитивный элемент поля, то произвольный ненулевой элемент представляется в виде степени а, т. е. β = αⁱ.

Тогда и, следовательно, все ненулевые элементы поля являются корнями уравнения хⁿ + 1 = 0. Эти корни принадлежат различным неприводимым в поле GF(2) многочленам, на которые разлагается двучлен xⁿ +1. Алгоритм такого разложения был приведен ранее. В частности, в примере 6.13 получена совокупность многочленов, корнями которых являются элементы поля Gf(24):

Для нас существенно, как распределены корни двучлена xⁿ+1 (а следовательно, и элементы поля) по составляющим неприводимым многочленам. Доказана следующая закономерность. Если известен один из корней β неприводимого многочлена степени m, то все другие корни этого многочлена являются определенными степенями β, а именно:

Порядок корней неприводимого многочлена является показателем, которому этот многочлен принадлежит.

Многочлен g(x) наименьшей степени, такой, что g(β)=0, называется минимальным многочленом для элемента β. Будем обозначать его gβ(x). Неприводимый над полем GF(2) многочлен степени т называется примитивным, если его корнем является примитивный элемент поля GF(2^m).

Пример 6.24. Найдем распределение корней двучлена

Если корни рассматривать как элементы поля, построенного с использованием неприводимого многочлена g(x) = x⁴ + x + 1, то этот многочлен является примитивным Действительно, примитивный элемент α поля GF(2⁴) является корнем многочлена g(x). Остальные его корни соответственно равны α², α⁴ и α⁸. Можно непосредственно убедиться в справедливости равенства

Теперь найдем минимальный многочлен g3(x) для элемента α³. Его корнями должны быть элементы

откуда

Аналогично определим минимальные многочлены g5(x) и g7(x) для элементов α⁵ и α⁷. Цикл корней g5(x) включает α⁵ и α¹⁰ соответственно для g7(x) имеем α⁷, α¹⁴, α¹³, α¹¹.

Следовательно,

Итак, распределено 14 корней многочлена x¹⁵ + 1. Последний корень α⁰ равен 1 и принадлежит двучлену x + 1.

Построение и реализация кодов. Процесс выбора образующего многочлена кода Боуза — Чоудхури — Хоквингема, рассчитанного на исправление единичных ошибок, ничем не отличается от рассмотренного ранее. Основное отличие заключается в интерпретации опознавателей ошибок. В данном случае ими считаются различные степени примитивного элемента поля GF(2^m), построенного с использованием выбранного неприводимого многочлена g(x) степени m, принадлежащего показателю степени n = 2^m—1. Так как число различных ненулевых элементов поля, выраженных степенями примитивного элемента, равно n, то каждому вектору ошибки в отдельном разряде можно сопоставить свой опознаватель, что и гарантирует возможность исправления ошибок.

При возникновении двух ошибок построенный код позволяет определить только сумму s опознавателей этих ошибок

где ξ, и ξ, — опознаватели ошибок в разрядах i и j.

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

Действительно,

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

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

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

откуда

Поскольку известны сумма и произведение опознавателей, то на основании теоремы Виета можно составить уравнение, для которого опознаватели ξ_i и ξ_j являются корнями:

Если ошибка оказалась одна, то

и ее опознаватель удовлетворяет уравнению

При отсутствии ошибок, естественно, получаем нулевые опознаватели, так как s₁=s₃ = 0.

На практике оказывается удобнее использовать многочлены, корнями которых являются не опознаватели ошибок, а их мультипликативные обратные элементы z= =ξ^-1.

Для случая исправления двойных ошибок левая часть уравнения преобразуется к виду

При возникновении одной ошибки

при отсутствии ошибок

Осталось выяснить, как получить суммы нечетных степеней опознавателей ошибок, в частности сумму 5з кубов опознавателей при исправлении двойных ошибок. Указанные суммы можно определить за счет последовательного добавления к выбранному примитивному многочлену g(x) в качестве сомножителей минимальных многочленов для элементов α³ (случай двойных ошибок), α⁵ (случай тройных ошибок) и т. д. Суммы нечетных степеней опознавателей ошибок вычисляются по остаткам, получаемым в результате деления принятой кодовой комбинации на соответствующий минимальный многочлен.

В общем случае образующий многочлен кода Боуза — Чоудхури — Хоквингема представляет собой наименьшее общее кратное (НОК) примитивного и минимальных многочленов

В частности, для кода с n =15, рассчитанного на исправление двойных независимых ошибок, получаем

Пример 6.25. Рассмотрим процесс исправления единичных ошибок кодом Боуза — Чоудхури (15, 11) с образующим многочленом g(x) = x⁴ + x + 1.

Используя табл. 6.23, сопоставим каждому вектору ошибки свой опознаватель в виде определенной степени примитивного элемента ее поля GF(2⁴) Результат представлен табл. 6.24.

Таблица 6.24

Схема декодирующего устройства представлена на рис 6.24. Детектор ошибки выполнен в соответствии с уравнением l+s1z = 0. За первые n = 15 тактов в результате деления поступающей из канала связи кодовой комбинации h(x) на g(x) получаем в регистре I опознаватель ошибки х^-j. Затем он переписывается в регистр II схемы, осуществляющей домножение опознавателя на α с приведением по модулю g(x), тес превращением α⁴ в α + 1.

На (n + 1)-м такте символ старшего разряда кодовой комбинации h(x) поступает из буферного регистра в сумматор коррекции. Одновременно производится домножение опознавателя α^-j на α, и на схему ИЛИ детектора подается вектор 1+si*α. Если 1 +s₁ α неравно 0, то s₁ неравно α^-1 и, следовательно, ошибка произошла не в старшем разряде.

Аналогично анализируется правильность других символов, последовательно поступающих в узел коррекции из буферного регистра. Когда в схеме коррекции появляется искаженный символ j-и позиции (начиная со старшего разряда), то 1+ +s₁α^j = 0 и s₁ = α^-j. При этом выходной сигнал схемы ИЛИ детектора равен нулю и импульс с выхода схемы НЕ корректирует ошибку.

Пример 6.26. Наметим последовательность операций при исправлении двойных ошибок кодом (15, 7) с образующим многочленом g(x) = (x⁴ + x + 1)(x⁴ + x³ + x² + x + 1).

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

1) нахождение суммы s₁ опознавателей ошибок путем деления поступившей из канала связи кодовой комбинации h(x) на многочлен х⁴ + x + 1;

2) определение суммы s3 кубов опознавателей в базисе α⁹ α⁶ α¹ путем деления h(x) на многочлен х⁴ + х³ + x² + x + 1;

3) выражение s₃ в базисе α³ α² α1;

4) вычисление s₁², отношения s₃/s₁ и суммы s₁² + s₃/s₁,

5) построение схемы для определения корней уравнения q(z) = 1+s₁z+(s₁² + + s₃/s₁)z² путем последовательного домножения s1 на α и (s₁² + s₃/s₁) на α².

§ 6.10. ИТЕРАТИВНЫЕ КОДЫ

Для итеративных кодов характерно, что операции кодирования проводятся над совокупностью информационных символов, располагаемых по нескольким, например q, координатам. В связи с этим итеративные коды также называют многомерными, многостепенными. Число информационных символов в кодовом векторе q-степенного кода

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

Классические итеративные коды. Идея создания рассматриваемых кодов принадлежит П. Элайесу.

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

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

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

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

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

Число ошибок такого вида В4 для блока из lхn символов равно

Общее число четырехкратных ошибок составляет

Таким образом, отношение числа не обнаруживаемых четырехкратных ошибок к общему числу таких ошибок

Определим минимальный вес ненулевого вектора рассматриваемого итеративного кода (двумерной кодовой комбинации). Такой вектор должен содержать только одну ненулевую вектор-строку, минимальный вес, которой равен 2. Проверка на четность каждого из ненулевых столбцов также дает вектор веса 2. Следовательно, минимальный вес ненулевого вектора итеративного кода с двойной проверкой на четность равен 2*2 = 4.

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

где dγ — кодовое расстояние линейного кода по координате γ.

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

Такая процедура проста, но снижает корректирующую способность итеративного кода, поскольку оказывается невозможным исправить часть ошибок кратности (d-l)/2.

Поясним это на примере итерации двух кодов Хэмминга (7, 4). Результирующий итеративный код (49, 16) имеет минимальное кодовое расстояние, равное 3x3 = =9, и, следовательно, потенциально, как любой линейный код, способен исправлять все ошибки кратности 4 и менее. Однако, применяя указанную выше процедуру декодирования, невозможно исправить четырехкратные ошибки с расположением искаженных символов в вершинах прямоугольника (рис. 6.26).

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

Рассмотрим один из таких кодов [4].

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

Расположение кодируемого кадра информации на ленте показано на рис. 6.27.

Кодирование циклическим кодом осуществляется следующим образом. Многочлен F1(x), соответствующий информации перкой строки, умножается на x и результат приводится по модулю образующего многочлена g(x) степени n, где n — число дорожек, включая контрольную [например, для 9 дорожек g(x) = (х + 1)(х⁸ + + х⁴ + х³ + x² + 1)]. Полученный остаток R_i(x) суммируется по модулю два с многочленом F2(x), соответствующим информации второй строки. Сумма снова умножается на x и далее приводится по модулю g(x), в результате чего определяется остаток R₂(x). Применив этот алгоритм последовательно ко всем строкам кодируемого кадра информации, получим R₁(x) — многочлен степени не выше n-1, который и записывается в конце кадра (при нечетном числе строк в нем), в качестве символов контроля по дорожкам

где R_i(x) mod (x) означает величину R_i(x), приведенную по модулю g(x).

Декодирование производится аналогично кодированию, причем участвует и контрольная строка — R_i(x). Процесс декодирования можно записать следующим образом:

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

Сравнивая его с выражением (6.58), можно заключить, что при отсутствии ошибки будет фиксироваться значение R'(x), равное нулю. Случай R'(x) неравна 0 соответствует обнаружению ошибки. Если имела место пачка ошибок вдоль одной из дорожек, то она может быть исправлена. Многочлен ошибки в этом случае имеет вид Ε (x) = x^je(х), где е(х) отражает поразрядную структуру, а х^j — адрес ошибки. Так как справедливо равенство (6.59), то

причем е(х) определяется по результатам проверок строк на нечетность.

Номер дорожки с искаженными символами может быть найден теперь, исходя из следующих соображений. Предположив, что на ленте была записана информация, состоящая из одних нулей, т. е. F₁(x) = 0...F_l(x) = 0, R_l(x) = 0 и при считывании на дорожке с выбранным известным номером n возникла пачка ошибок с точно такой же структурой е(х), в результате декодирования получим некоторый многочлен R"(x), причем

где k — число дорожек, на которое отстоит дорожка с известным номером η от дорожки, где возникла пачка ошибок.

Таким образом, если пачка ошибок возникла только по одной дорожке, то, умножив R'(x) на x^k с приведением по модулю g(x), получим R"(x). Поэтому при декодировании одновременно с вычислением R'(x) осуществляется вычисление R"(x). Для определения номера дорожки с искаженными символами производится последовательное домножение R'(x) на х, х²,..., х^n-1.

На каждом шаге, начиная с R'(x), результат приводится по модулю g(x) и затем сравнивается с R"(x). Процесс прекращается, как только на каком-либо i-м шаге зафиксировано равенство (в этом случае k = i— 1 и известная величина n определяет номер искомой дорожки) или после проведения n сравнений. В последнем случае фиксируется наличие неисправимой ошибки.

При четном числе строк кодируемой информации l образующий многочлен типа g(x) = (х + 1)g'(x) обеспечивает R_l(x) всегда с четным числом членов. Суммирование этого многочлена с g'(x) позволяет получить результирующий многочлен R'_l(x), удовлетворяющий проверке по нечетности вдоль строки.

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

где L(x) — произвольный многочлен.

Кодирование и декодирование информации с использованием рассматриваемых кодов относительно просто реализуется как программными, так и аппаратными средствами [4].

§ 6.11 СВЕРТОЧНЫЕ КОДЫ

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

В общем случае сверточному кодированию могут подвергаться последовательности символов, являющихся элементами произвольного конечного поля GF(q). Мы ограничимся рассмотрением двоичных сверточных кодов. Принцип кодирования поясняется рис. 6.28. В каждый дискретный момент времени на вход кодирующего устройства поступают k информационных последовательностей символов, а с его выхода в канал связи выдаются η последовательностей, причем n>k. Проверочные символы, как и в блоковых кодах, получаются в результате проведения линейных операций над определенными информационными символами.

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

Способы реализации сверточных кодов во многом похожи на способы реализации циклических кодов.

Процессы кодирования и декодирования таких кодов можно описать посредством многочленов с использованием оператора задержки D. Последовательности символов, поступающие на каждый из входов, представляют многочленами, где c_t⁽ⁱ⁾— символ, появляющийся на j-м выходе кодирующего устройства в момент τ.

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

Степени образующих многочленов не превышают числа т, а коэффициентами Mjk для двоичных кодов являются элементы поля GF(2).

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

где b_t⁽ⁱ⁾ — символ j-и информационной последовательности, поступившей в момент τ.

Последовательности проверочных символов также можно записать в виде многочленов

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

здесь U_t⁽ⁱ⁾ символ j-й информационной последовательности, поступившей в момент τ(j=1,2,…,k); U_t⁽ⁱ⁾ — символ i-й проверочной последовательности, поступившей в момент τ(i= k+l, k + 2,...,n).

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

где e_t^(j) — символ ошибки, имеющей место в j'-й информационной последовательности в момент τ (у = 1, 2,..., k).

где e_t⁽ⁱ⁾ — символ ошибки, имеющей место в i-й проверочной последовательности в момент τ (i = k + 1, k + 2,..., n).

Очевидно,

В процессе декодирования по информационным символам, поступающим из канала связи, с использованием образующих многочленов снова формируются последовательности проверочных символов U_l⁽ⁱ⁾(D)

Последовательности U_l⁽ⁱ⁾(D) и U⁽ⁱ⁾(D) (i = k+l, k + 2,..., n) сравниваются между собой, в результате чего получаем последовательности S⁽ⁱ⁾(D), определяющие структуру ошибок. Эти последовательности по аналогии с блоковыми кодами называют синдромами

Подставляя выражения (6.63) и (6.64) в (6.66), получаем

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

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

На рис. 6.29 приведена схема кодирующего устройства для простейших сверточных кодов, у которых на k информационных символов приходится один проверочный. За время цикла входной коммутатор СК₁ направляет k символов входной последовательности в k информационных каналов, с которых они поступают как непосредственно на выход, так и на линейный преобразователь П, формирующий проверочный символ C_k+1· В случае двоичного кодирования преобразователь включает ячейки памяти, объединенные в регистры сдвига, устройства умножения на постоянную величину (связи) и сумматоры по модулю два. Ячейки памяти позволяют добиться усреднения влияния помехи при малых n за счет использования символов, поступающих на соседних циклах.

В декодирующем устройстве (рис. 6.30) информационные символы последовательности, поступающей из канала связи, также разделяются с помощью коммутатора CK₁ по k информационным каналам. Посредством линейного преобразователя П, аналогичного преобразователю кодирующего устройства, снова формируются проверочные символы C_k+1, которые сравниваются (суммируются по модулю два) с проверочными символами, поступающими непосредственно из канала связи. В случае отсутствия ошибок образующаяся на выходе последовательность символов состоит из одних нулей.

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

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

Пример 6.27. Рассмотрим процессы кодирования и декодирования простейших сверточных кодов, разработанных Д. В. Хагельбаргером.

Для формируемых этим кодом последовательностей характерно, что за каждым информационным символом следует проверочный символ (n = 2, k= 1). Коды способны исправлять пачку ошибок длиной <l символов при условии, что две соседние пачки разделены между собой защитным промежутком 3l+1 символов, т.е. между последним символом данной пачки и первым символом следующей пачки должно быть не менее 3l+ 1 неискаженных символов.

Для конкретности примем l<4. Кодирующее устройство такого кода (рис. 6.31) представляет собой схему умножения на образующий многочлен G(D) = D² + D⁴ (см. рис. 6.11). Будем считать, что на вход поступает последовательность информационных символов (точка Κι) 100100111001, что соответствует многочлену B(D) = 1 + D³ + D⁶ + +D⁷+D⁸ + D¹¹.

Помножив B(D) на образующий многочлен G(D), получим многочлен C(D), соответствующий последовательности проверочных символов, формируемых в точке К₂:

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

Таблица 6.25

При последовательной передаче с выхода коммутатора будут поступать попеременно информационные символы последовательности 1001001110010000 и проверочные символы из последовательности 0010110111011101, образуя на входе канала связи последовательность (в точке К₃) 10000110010110111101001101010001.

Предположим, что в канале связи произошло искажение 7, 8 и 9-го символов. Последовательность на выходе канала связи (точка K₄) имеет вид 100001 101101111010011, где искаженные символы помечены прямоугольником.

Последовательность информационных символов в декодирующем устройстве (точка K₅) 100010111001 соответствует многочлену

а последовательность проверочных символов 0011110111011 — многочлену U⁽²⁾(D)= = G(D) + С^(c)(D), где E^(c)(D) = =D³.

Декодирующее устройство (рис. 6.32) состоит из двух частей: первая часть вырабатывает опознаватель ошибки (синдром), а вторая — анализирует синдром и производит само исправление (узел коррекции).

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

Процесс ее формирования показан в табл. 6.26. Сформированная в точке a последовательность сравнивается с последовательностью проверочных символов, поступающих из канала связи, в результате чего на выходе (точка К₆) вырабатывается опознаватель ошибки — синдром S(D):

Таблица 6.26

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

Первые две позиции в синдроме характеризуют искажения в проверочных символах (E^(c)(D)), затем две позиции характеризуют искажения в информационных символах (D²E^(b)(D)), а в следующих двух позициях предыдущие значения повторяются ( D⁴E^(b)(D)).

Убедимся, что последовательность в точке K₆ декодирующего устройства соответствует полученному синдрому. Она равна сумме по модулю два последовательности в точке a и последовательности поступивших из канала проверочных символов

Полученная последовательность действительно соответствует

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

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

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

На выходе элемента И получаем последовательность импульсов коррекции, исправляющих поступившую последовательность информационных символов Запишем эти последовательности:

Так как корректирующий сигнал формируется через 3l/2, а информационные символы задерживаются только на l тактов, то возникает необходимость в дополнительной задержке информационных символов на l/2 тактов (l/2 = 2) Это осуществляется блоком задержки. Совместно с сумматором по модулю два он образует устройство исправления ошибок:

последовательность в точке K₅ 100010111001

последовательность в точке Κ₇ 00000110000000

исправленная последовательность

информационных символов

(точка K₈) 00100100111001

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

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

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

Таким образом, информационным последовательностям в синдроме соответствуют конфигурации веса второго вида:

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

Для проверочной последовательности имеем единственную конфигурацию веса первого вида E^(k+1) 0...0. Конфигурации в синдроме кода должны быть размещены так, чтобы они не накладывались друг на друга, обеспечивая их безошибочное выделение при декодировании.

Для сверточного кода, рассчитанного на исправление пачек ошибок длины l при считывании с накопителя, имеющего k0 информационных дорожек и одну проверочную n₀ = (k₀+1), общее выражение для синдрома информационной последовательности имеет вид

где E^(j)(D) — двоичная последовательность, соответствующая пакету длины l, возникшему на j-и дорожке (1<=j<=k₀).

Аналогичное выражение для синдромов ошибок на контрольной дорожке имеет вид

где E⁽ⁿ⁰⁾(D) — двоичная последовательность, соответствующая пакету ошибок длиной l, возникшему на контрольной дорожке.

Связь между символами синдрома и символами принятой последовательности задается посредством выражения (6.67), считая, что на всех дорожках, кроме j-и, пакеты ошибок отсутствуют (соответствующие E(D) нулевые), синдромы S⁽ⁿ⁰⁾(D) для различных j можно представить в виде

где G_(n0)^(j)(D) — образующие многочлены сверточного кода.

Подберем G_(n0)^(j)(D) так, чтобы при возникновении последовательности ошибок E^(j)(D) синдром S⁽ⁿ⁰⁾ (D) соответствовал выражению 1.

Указанным требованиям удовлетворяет образующие многочлены вида

Защитный промежуток построенного кода

здесь m — наибольшая степень образующего многочлена.

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

Для построения кода К₀ информационных последовательностей, поступающих на вход кодера, представим в виде

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

Подставляя образующие многочлены (6.73) в выражение для контрольной последовательности, получим значения символов этой последовательности, которая имеет вид

Таким образом, при выбранных образующих многочленах контрольную последовательность символов С⁽ⁿ⁰⁾(D) можно представить в виде двух последовательностей, которые при n₀ — k₀ = 2 могут быть записаны на две контрольные дорожки. Тогда по одной дорожке фиксируется последовательность

а на другой контрольной дорожке — последовательность

Рассмотрим процесс исправления ошибок. Запишем общие выражения для синдромов ошибок каждой из контрольных последовательностей

где

где

Тогда

Поскольку предполагается, что пакеты ошибок возникают только по одной дорожке, один из синдромов определяет начало пакета и его структуру и, следовательно, дает информацию о виде многочлена ошибки Ε (D). Структура другого синдрома в этом случае должна иметь вид E(D)D^j-1. Для определения номера дорожки, где расположен пакет ошибок, последовательно домножаем Ε (D) на D и сравниваем с другим синдромом. Значение j, при котором наступает равенство, указывает номер искомой дорожки.

Процесс образования контрольных символов имеет простое толкование. Если совокупность образующих код многочленов, участвующих в формировании символов контрольной последовательности С^(k0+1)(D), записать в виде

а совокупность образующих многочленов, участвующих в формировании символов контрольной последовательности G^(k0+2)(D), в виде

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

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

где т — наибольшая из степеней образующих многочленов.

Для реализации разработанного кода требуется простая аппаратура с буферной памятью, емкостью &0по разрядов. Схема кодирующего устройства приведена на рис. 6.34, а схема декодирующего устройства — на рис. 6.35. Поскольку процесс кодирования не требует пояснений, остановимся только на процессе декодирования.

Поиск по сайту: