52. Циклический код. Обнаpужение и испpавление ошибок. Оценка помехоустойчивости.

Ошибочная комбинация циклического кода представляется следующим образом:

В основе методов обнаружения и исправления ошибок лежат соотношения (2.3) и (2.4). При коррекции ошибок с использованием свойства образующего полинома (2.3) определяется синдром (опознаватель) ошибок длины k

В декодирующих устройствах соотношения (2.6) или (2.7) реализуются вычислителем синдрома. Если синдром d(x) ≠ 0, то это говорит о наличии ошибок в принятой кодовой комбинации. Число возможных ненулевых син-дромов M = 2 в степени k −1. Если полиному ошибок l(x) соответствует индивидуальный синдром d(x), то по виду синдрома можно найти полином ошибок и исправить принятый кодовый полином путем его сложения по mod 2 с полиномом ошибок, т.е. Если разным ошибкам отвечает один и тот же синдром d(x), то такие ошибки не различаются и их можно только обнаружить. Вместо (2.6) набор синдромов удобно получать непосредственно из проверочной матрицы Hk,n в канонической форме. Синдром (2.7) удобно получать из проверочной матрицы H в степени *k,n в циклической форме. Однако для этого матрицу H в степени *k,n нужно достроить циклическим сдвигом вправо ее строк до квадратной матрицы H в степени *n,n ранга n. Тогда столбцы этой матрицы представляют собой n-разрядные синдромы одиночных ошибок в соответствующих им разрядах кодовой комбинации. Остальные синдромы находят поразрядным суммированием по mod 2 столбцов матрицы в разных сочетаниях. А) Обнаружение ошибок по синдрому. Структура декодера циклического кода по синдрому в режиме обнаружения ошибок представлена на рис

Принцип работы. Кодовая комбинация циклического кода поступает од-новременно в n-разрядный буферный регистр сдвига БРС и k-разрядный вычислитель синдрома старшим разрядом вперед. Время декодирования, измеряемое в тактах генератора тактовых импульсов ГТИ, определяется вре-менем вычисления синдрома, которое составляет n тактовых импульсов(ТИ). Обнаружение ошибок осуществляется на (n+1)-м такте работы декодера. Если d(x)≠0, то Z=0 и формируется сигнал "Стирание" (считывание информации при этом не происходит). Б) Исправление ошибок по синдрому. Пусть код (n,m) может исправлять все ошибки кратности S. Тогда число исправляемых ошибок равно числу индивидуальных синдромов

Для исправления ошибок нужно знать полином ошибок l(x). В декоди-рующих устройствах полином l(x) формируется специальной решающей схемой − селектором синдромов. Возможны два способа определения полинома ошибок l(x) − параллельный и последовательный. 1. Параллельный способ. Структура декодера по синдрому в режиме исправления ошибок параллельного действия (рис.2.28). Здесь селектор настраивается на N синдромов. Он формирует соответствующие им полиномы ошибок. Такой селектор − это комбинационная схема, на вход которой подается комбинация синдрома, а с выхода снимается

параллельным кодом полином ошибки l(x).

Ошибка исправляется парал-лельным поразрядным суммированием искаженного кодового полинома β′(x) и полинома ошибки l(x) с помощью многовходового сумматора. Сложность селектора определяется числом N селектируемых синдромов. Она быстро растет с ростом S и n. Например,

2) Последовательный способ. Этот способ определения l(x) позволяет уменьшить сложность селектора синдромов. Он использует свойство цик-личности кода и базируется на операции циклического сдвига синдрома в его вычислителе

Из канала связи обычно первым поступает старший разряд. При наличии в нем ошибки он первым же должен исправляться. Поэтому, в качестве кор-ректоров выбирают синдромы, которым соответствуют комбинации ошибок с единицей на позиции старшего разряда. Селектор синдромов настраивается на Т корректоров. Вычисленный синдром ошибок d(x) циклически сдвигается влево (т.е. в сторону старших разрядов) в вычислителе синдрома до совпадения с одним из корректоров. Совпадение фиксируется селектором. Вид корректора, с которым совпал сдвигаемый синдром и число его шагов сдвига q до совпадения, определяют искаженные разряды. Отсутствие совпадения с корректорами при изменении q от 0 до (n-1) говорит о наличии обнаруженных и неисправленных ошибок. Число Т корректоров d*(x) растет с ростом n и S.

Поэтому область применения последовательного способа декодирования ограничивается кодами с S=1 и S=2. Рассмотрим алгоритм исправления одиночных ошибок (S=1), например, на основе полинома h(x). Алгоритм определяется выражением

Действие алгоритма состоит в следующем. Корректор вычисляется по формуле (2.7) и известен заранее. На этот корректор настраивается селектор синдромов. Число корректоров Т=1 при S=1. При коррекции полинома β′(x) вычисляется на основании (2.7) синдром d(x). Если d(x) ≠ 0, то в (2.8), начиная с нуля, последовательно изменяется q до выполнения равенства. Полученное значение q позволяет указать номер искаженного разряда, равный (n-1)-q. Если при изменении q от 0 до (n-1) равенство (2.8) не выполняется, то это говорит о наличии неисправляемой ошибки.

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

Принцип работы. Символы кодовой комбинации β' последовательно, на-чиная со старшего разряда, вводятся в n-разрядный БРС и одновременно в k-разрядный вычислитель синдрома, где за n тактов сдвига определяется оста-ток от деления кодового полинома β'(x) на образующий полином p(x). Затем в декодере производится еще n тактов сдвига. С каждым сдвигом буферный регистр покидает один символ, а в вычислителе синдрома появляется новый синдром. Этот синдром будет совпадать с одним из корректоров, когда каждый из ошибочных символов занимает крайнюю правую ячейку БРС. При этом селектор синдромов-корректоров формирует логическую единицу (Y=1), которая, воздействуя на сумматор коррекции М2, исправляет искаженный символ. Исправленный символ покидает декодер при следующем такте сдвига. Одновременно логическая единица с выхода селектора подается в вычислитель синдрома, модифицируя синдром так, чтобы он снова соответствовал более простому полиному ошибок, которые еще подлежат исправлению. После исправления последней ошибки все ячейки памяти вычислителя синдрома должны оказаться в нулевом состоянии. Противный случай означает, что имеет место неисправляемая ошибка. Конечное состояние вычислителя синдрома фиксируется селектором нулевого синдрома. Обнаружение неисправляемых ошибок производится на

(2n+1)-м такте сдвига, подобно схеме декодера на рис. 2.27.

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

принимаемыми кодовыми полиномами должны составлять не менее n тактов.

Вычислитель синдрома здесь, в отличие от декодера на рис. 2.27, имеет

дополнительную связь для модификации синдрома. Основу модификации

составляет синдром-корректор одиночной ошибки в

старшем (n-1)-м разряде кодовой комбинации. Объясняется это тем, что любой синдром S ошибок может быть представлен как сумма по модулю 2 S синдромов одиночных ошибок (соответствующих столбцов проверочной матрицы). Поэтому каждый корректор в подобной сумме обязательно содержит синдром одиночной ошибки в старшем разряде.

Следует отметить, что при S=1 модификация − это просто сброс вычислителя синдрома.

Помехоустойчивость циклического кода. Помехоустойчивость оценивается:

⎯ вероятностью неправильного декодирования PНД;

⎯ вероятностью правильного декодирования PПД;

⎯ вероятностью стирания кодовой комбинации при декодировании PСД.

Эти три вероятности образуют полную группу событий. Тем самым

Вероятности определяются в зависимости от режима декодирования.

А) Декодирование в режиме обнаружения r ошибок (d ≥ r −1) .

В этом режиме при обнаружении ошибок принятая кодовая комбинация

β' стирается. В остальных случаях комбинация выдается получателю. Неправильное декодирование имеет место в том случае, когда комбинация ошибки l отлична от нуля и совпадает с безошибочной комбинацией β. Тогд