Никитин Г.И. Помехоустойчивые циклические коды

Подождите немного. Документ загружается.

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Санкт-Петербургский

государственный университет аэрокосмического приборостроения

Г. И. Никитин

П О М Е Х О У С Т О Й Ч И В Ы Е

Ц И К Л И Ч Е С К И Е

К О Д Ы

Учебное пособие

Санкт-Петербург

2003

Никитин Г. И.

Помехоустойчивые циклические коды: Учеб. пособие/СПбГУАП.

В пособии даётся классификация разновидностей, характеристик и параметров корректирующих

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

ческих кодов, их определение, свойства и эффективность, а также реализация кодирующих и

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

применения циклических кодов и линейных переключательных схем в радиотехнических систе-

мах, в том числе в космических системах передачи информации. Рассмотрен порядок выполнения ла-

бораторной работы " Циклические коды".

Пособие предназначено для студентов, изучающих специальность "Радиотехника".

Список основных сокращений

АКФ - автокорреляционная функция

АРБ - аварийный радиобуй

АТС - автоматическая телефонная станция

БРК - бортовой радиокомплекс

ВКФ - взаимнокорреляционная функция

ДУ - декодирующее устройство

ЗНД - защита от несанкционированного доступа

ЗУ - запоминающее устройство

ИКАО - Международная организация гражданской авиации

ИМО - Международная морская организация

ИС - источник сообщений

ИСЗ - искусственный спутник Земли

ИЦСС - интегрально-цифровые системы связи

КЭАТС - квазиэлектронные АТС

КУ - кодирующее устройство

Коды:

БЧХ - Боуза-Чоудхури-Хоквингема

РС - Рида-Соломона

ЦК - циклические коды

НДК - натуральный двоичный код

СДК - симметричный двоичный код

КПВ - код с постоянным весом

КПЧ - код с проверкой на чётность

Л П С - линейная переключательная схема

МККТТ - Международный консультативный комитет по телефонии и

телеграфии

ММП - метод максимального правдоподобия

ОКС - общий канал сигнализации

ОФМ - относительная фазовая модуляция

ПС - получатель сообщений

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

П П И - пункт приёма информации

ППРЧ - программная перестройка рабочих частот

СМД - синдромный метод декодирования

СПД - система передачи данных

СР - сдвигающий регистр

ТИ - тактовый импульс

ЦС - центр системы

ЧВМ - частотно-временная матрица

ЭМС - электромагнитная совместимость

Лабораторная работа № 4

“ИССЛЕДОВАНИЕ ЦИКЛИЧЕСКИХ И БЧХ-КОДОВ”

ЦЕЛЬ РАБОТЫ: изучение принципов помехоустойчивого кодирования,

ознакомление с циклическими и БЧХ-кодами, с методами кодирования и

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

примере циклических кодов (15,k) и БЧХ-кода (15,7).

ВВЕДЕНИЕ

В настоящее время, в связи с многократно возросшими объёмами пере-

даваемой и сохраняемой информации, ужесточились требования к её досто-

верности. Одним из самых перспективных методов решения этой проблемы явля-

ется помехоустойчивое кодирование на основе корректирующих кодов. В послед-

нее время коды, исправляющие ошибки, нашли применение во многих системах

передачи и хранения информации. Наиболее известные из них – это сотовые сис-

темы связи, спутниковая спасательная система КОСПАС — САРСАТ, система

глобальной морской связи ИНМАРСАТ, различные системы спутниковой теле-

фонной связи, накопители информации на магнитных дисках, система звукозапи-

си на компакт-дисках и др. Во всех вышеприведённых примерах систем с помехо-

защищённой обработкой информации используются наиболее простые и эффек-

тивные циклические корректирующие коды, которые, наряду с простотой кодиро-

вания и декодирования, отличаются достаточно большой корректирующей спо-

собностью. Изучению этих кодов посвящена лабораторная работа.

1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ

К ЛАБОРАТОРНОЙ РАБОТЕ

Для выполнения лабораторной работы студенты должны предварительно

изучить раздел 1 настоящего методического руководства и получить у преподава-

теля допуск к работе.

1.1. Классификация корректирующих кодов

С классификацией корректирующих кодов студенты уже знакомы по мате-

риалам, приведённым в ЛР №3. В связи с этим напомним только основные

положения, касающиеся циклических кодов.

Все корректирующие коды можно разделить на два класса: блочные и не-

прерывные.

Блочные коды — коды, в которых каждому сообщению (или элементу) сопос-

тавляется блок из n символов (кодовый вектор длиной n). Операции кодирования и

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

Непрерывные коды представляют собой непрерывную последовательность

символов, не подразделяемую на блоки. Такие коды называются также рекуррент-

ными, цепными, свёрточными, конволюционными. Процессы кодирования и декоди-

рования осуществляются непрерывно. Передаваемая последовательность образуется

путём размещения в определённом порядке проверочных символов между инфор-

мационными символами исходной последовательности.

Как блочные, так и непрерывные коды делятся на разделимые и нераз-

делимые.

Разделимые коды предусматривают возможность чёткого разграничения ин-

формационных и проверочных символов.

Неразделимые коды не предусматривают такой возможности и к ним от-

носятся, например, коды с постоянным весом (КПВ).

Разделимые коды делятся, в свою очередь, на систематические (линейные

или групповые) и несистематические (нелинейные).

Систематические коды характеризуются тем, что сумма по модулю 2 двух

разрешённых кодовых комбинаций кодов этого класса снова даёт разрешённую ко-

довую комбинацию.

Кроме того, в систематических кодах информационные символы, как прави-

ло, не изменяются при кодировании и занимают определённые заранее заданные

места. Проверочные символы вычисляются как линейная комбинация информаци-

онных, откуда и возникло другое наименование этих кодов — линейные. Для сис-

тематических кодов принимается обозначение [n, k] - код, где k — число информа-

ционных символов в кодовой комбинации, n — общее число символов в коде.

Несистематические коды не обладают отмеченными выше свойствами и

применяются значительно реже, чем систематические, в частности, в несиммет-

ричных каналах связи. К этому классу кодов относятся такие, например, коды как

КПВ, итеративные, комбинационные и антифединговые [3].

Циклические коды составляют большую группу наиболее широко используемых на

практике линейных, систематических кодов. Их основное свойство, давшее им назва-

ние, состоит в том, что каждый вектор, получаемый из исходного кодового вектора пу-

тём циклической перестановки его символов, также является разрешённым кодовым

вектором. Принято описывать циклические коды (ЦК) при помощи порождающих по-

линомов G(Х) степени r = n — k, где r — число проверочных символов в кодовом слове.

В связи с этим ЦК относятся к разновидности полиномиальных кодов.

Операции кодирования и декодирования ЦК сводятся к известным процедурам

умножения и деления полиномов. Для двоичных кодов эти операции легко реализуются

технически с помощью линейных переключательных схем (ЛПС), при этом получаются

относительно простые схемы кодеков, в чём состоит одно из практических достоинств

ЦК.

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

Боузом и Чоудхури и независимо от них Хоквингемом. Коды Боуза—Чоудхури-

Хоквингема получили сокращённое наименование БЧХ- коды.

БЧХ- коды являются обобщением кодов Хемминга на случай исправления не-

скольких независимых ошибок (g

>1). Частными случаями БЧХ- кодов являются коды

Файра, предназначенные для обнаружения и исправления серийных ошибок ("пачек"

ошибок), код Голея - код, исправляющий одиночные, двойные и тройные ошибки

min

=7), коды Рида-Соломона (РС- коды), у которых символами кода являются много-

разрядные двоичные числа.

1.2. Полиномиальное определение циклических кодов и операции с ними

Циклические коды являются частным случаем систематических, линейных [n, k]-

кодов. Название ЦК получили из-за своего основного свойства: циклическая переста-

новка символов разрешённой кодовой комбинации даёт также разрешённую кодовую

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

слева направо на одну позицию, причем крайний справа символ переносится на место

крайнего левого.

Если, например, А

- 101100, то разрешённой кодовой комбинацией будет и

- 010110, полученная циклической перестановкой. Отметим, что перестановка про-

изводится вместе с проверочными символами, и по правилам линейных кодов сумма

по модулю 2 двух разрешённых кодовых комбинаций даёт также очередную разрешён-

ную кодовую комбинацию.

Описание ЦК связано с представлением кодовых комбинаций в виде полино-

мов (многочленов) фиктивной переменной "X". Для примера переведём кодовое слово

= 101100 в полиномиальный вид

654321

к о д 101100

При этом А

(X) = 1 · X

+ 0 · X

+ 1 · X

+ 0 · X

= X

+ X

Действия с кодовыми векторами, представленными в виде полиномов, произ-

водятся по правилам арифметики по модулю 2, в которой вычитание равносильно

сложению. Так, из равенства Х

-1 = 0 получаем Х

=1. Прибавив к левой и правой час-

тям по единице, имеем Х

+ 1 = 1 ⊕ 1= 0. Таким образом, вместо двучлена Х

-1 можно

ввести бином Х

+1 или 1 + Х

, из чего следует, что Х

⊕ Х

= Х

(1 ⊕ 1) = 0 и при по-

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

ременных X с одинаковыми степенями.

Приведём далее порядок суммирования (вычитания), умножения и деления по-

линомов с учётом того, что операция суммирования осуществляется по модулю 2. В

примерах используем вышеприведённые кодовые комбинации А

(X) = X

+ X

(X) = X

+ X

+ X.

Суммирование (вычитание):

+ А

= А

- А

= X

+ X

+ X = X

+ X

или А

101100

⊕

010110

_______

111010 = X

+ X

+ X.

Умножение:

× А

( X

+ X

) × ( X

+ X

+ X) = X

+ X

= X

= 1000101000.

Деление:

+ X

│

+ X

- │——————

+ X

——————

0 0 0 - остаток при делении R(X) = 0.

Из последнего примера следует, что при циклическом сдвиге вправо на один раз-

ряд необходимо исходную кодовую комбинацию поделить на X, а умножение на

экви-

валентно сдвигу влево на один символ.

На основании того, что будет сказано далее о ЦК, нельзя установить теоретиче-

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

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

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

работки ЦК.

1.3. Порождающие полиномы циклических кодов

Формирование разрешённых кодовых комбинаций ЦК B

(X) основано на пред-

варительном выборе так называемого порождающего (образующего) полинома G(X),

который обладает важным отличительным признаком: все комбинации B

(X) делятся

на порождающий полином G(X) без остатка, т. е.

),)X(R()X(A

)X(G

)X(B

0==

остаткепри

(4.1)

где А

(Х) — информативный полином (кодовая комбинация первичного кода, преоб-

разуемого в корректирующий ЦК).

Поскольку, как отмечалось выше, ЦК относятся к классу блочных разделимых ко-

дов, у которых при общем числе символов n число информационных символов в А

(Х)

равно k, то степень порождающего полинома определяет число проверочных симво-

лов r = n - k.

Из этого свойства следует сравнительно простой способ формирования разре-

шённых кодовых комбинаций ЦК — умножение комбинаций информационного кода

(Х) на порождающий полином G(X):

(X) = A

(X)·G(X). (4.2)

В теории циклических кодов доказывается, что порождающими могут быть толь-

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

+1:

).)X(R()X(H

)X(G

остаткепри (4.3)

Возможные порождающие полиномы, найденные с помощью ЭВМ, све-

дены в обширные таблицы. Так, в [6] приведены таблицы G(X) с записью полино-

мов в восьмеричной системе счисления (mod 8). В этом случае весовые коэффи-

циенты k

представляют три двоичных знака в соответствии со следующим кодом:







111 - 7 101 - 5 011 - 3 001 - 1

110 - 6 100 -4 010 - 2 000 - 0

(4.4)

Двоичные символы являются весовыми коэффициентами порождающих

полиномов, коэффициенты восьмеричной системы счисления расположены слева

от них с учётом того, что 0 ≤ k

≤ 7 (при mod 8). Например, 3425 обозначает много-

член 10-й степени, В двоичной записи числу 3425 (mod 8) эквивалентно число

011100010101 и соответствующий многочлен равен X

+ X

+ 1. Как

видно из этого примера, восьмеричная система счисления для записи многочле-

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

раза при больших объёмах табулированных значений, что подчёркивает извест-

ный недостаток двоичной системы счисления.

Некоторые из порождающих полиномов приведены в табл. 1.

Следует отметить, что с увеличением максимальной степени порождающих

полиномов r резко увеличивается их количество. Так, при r = 3 имеется всего два

полинома, а при r = 10 их уже несколько десятков.

Первый порождающий полином минимальной степени r=1, удовлетворяющий

условию (4.3), формирует код с проверкой на чётность при двух информативных

символах и одном проверочном, обеспечивающем обнаружение однократной

ошибки, поскольку минимальное кодовое расстояние d

min

= 2. В общем случае ко-

эффициент избыточности КПЧ минимален:

r 1

==κ (4.5)

а относительная скорость кода – максимальна и равна

−

== (4.6)

В связи с этим КПЧ иногда называют быстрым кодом.

Таблица 1

степень

полинома

G(X)

Порождаю

щий полином

G(X)

Запись

поли

нома по

mod 2

Запись поли

нома по

mod 8

n k

Примечание

1X+1 11 3 32

Код с п

ове

кой на

чётность (КПЧ)

+X+1 111 7 3 1

Код с повторением

+X+1

1101

1011

Классический код

Хемминга

+ X+1

+X+1

11001

10011

10111

11101

Классический код

Хемминга

Коды Файра-

Абрамсона

. . .

100101

101001

Классический код

Хемминга

. . .

1111111 177 7 1

Код с повторением

Второй порождающий полином степени r =2, являющийся "партнёром" пер-

вого G(X) = X+ 1 при разложении бинома с n = 3, определяет код с повторением

единственного информативного символа k =1 ("0" или "1").

Отметим, что ЦК принадлежат к классу линейных кодов, у которых кодовые

комбинации "000 ... 00" и "111... 11 " являются разрешёнными.

У кода с повторением возможности обнаружения и исправления ошибок без-

граничны, поскольку число повторений ℓ [1] определяет минимальное кодовое рас-

стояние:

min

= ℓ. (4.7)

В общем случае коэффициент избыточности кодов с повторением кодовых

комбинаций является максимально возможным:

l 1

−=

−

=κ

и при увеличении ℓ приближается к 1, а скорость (4.6) - минимальна

1 =κ−= (4.8)

Таким образом, коды с проверкой на чётность и коды с повторением - до не-

которой степени антиподы. Первый код очень быстр (всего один дополнительный

символ), но зачастую "легкомыслен". Возможности второго кода с повторением по

исправлению ошибок теоретически безграничны, но он крайне "медлителен" [7].

Следующие порождающие полиномы в табл. 1 со степенью r = 3 позволяют

сформировать набор классических корректирующих кодов Хемминга (7, 4), которые ис-

следовались студентами ранее при выполнении лабораторной работы N3 "Корректи-

рующие коды". Коды Хемминга также принадлежат к классу ЦК, однако при этом гpyппa

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

кодовой группы на порождающий полином, а не "поэлементно", как это показано в

ЛР №3, когда последовательное суммирование по модулю 2 соответствующих ин-

формативных символов давало очередной символ проверочной группы. Отметим, что

два варианта порождающих полиномов кода Хемминга (7,4), с записью по модулю 2 в

виде 1101 и 1011, представляют собой так называемые двойственные многочлены (по-

линомы).

Двойственные многочлены определяются следующим образом: если задан по-

лином в виде

h(X) = h

X + h

+ … + h

то двойственным к нему полиномом является

,h...XhXh)X(h

1rr

+++=

−

(4.9)

т. е. весовые коэффициенты исходного полинома, зачитываемые слева направо, стано-

вятся весовыми коэффициентами двойственного полинома при считывании их справа

налево. Говоря образно, набор весовых коэффициентов "вывёртывается наизнанку".

Обратим внимание на то, что в полных таблицах порождающих ЦК полиномов

двойственные полиномы, как правило, не приводятся [6].

Наряду с тем, что порождающие полиномы кода Хемминга (7,4) являются двой-

ственными друг другу, они также являются неприводимыми.

Неприводимые полиномы не делятся ни на какой другой полином степени меньше

r, поэтому их называют ещё неразложимыми, простыми и примитивными.

Далее в табл. 1 при значениях r = 4 и 5 попадают следующие классические ко-

ды Хемминга (15, 11) и (31, 26). Порождающие их полиномы также являются двойст-

венными друг к другу и неприводимыми. Напомним, что к классическим кодам Хемминга

относятся коды, у которых n = 2

- 1, a k = 2

-1- r [3], с минимальным кодовым расстоя-

нием d

min

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

При значениях r = 4 в табл. 1 попадают двойственные порождающие многочлены

кода Абрамсона (7, 3), являющиеся частным случаем кодов Файра, порождающие поли-

номы для которых имеют вид

G(X) = p(X) · (X

+ 1), (4.10)

где р(Х) - неприводимый полином.

Коды Абрамсона совпадают с кодами Файра, если положить с = 1. Число прове-

рочных символов r = 4 определяет общее число символов в коде (значность кода), по-

скольку для этих кодов n = 2

r-1

- 1. Эти коды исправляют все одиночные и смежные

двойные ошибки (т.е. серии длиной 2). Помещённые в табл. 1 коды Абрамсона (7,3) яв-

ляются первыми циклическими кодами, исправляющими серийные ошибки (пакеты

ошибок). В этом применении ЦК оказываются особенно эффективными. Обратим

внимание на то, что при с =1 в (4.10) порождающими полиномами р(X) являются двой-

ственные полиномы X

+ X

+ 1 и X

+ X+ 1, образующие код Хемминга (7, 4) при r = 3.

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

щений помех импульсного характера, длительность которых больше длительности од-

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

щая длительность которых соответствует длительности помехи.

В заключение на основании данных табл. 1 приведём все возможные порождаю-

щие полиномы для кодовых комбинаций с числом символов n = 7.

В соответствии со свойством (4.3) порождающих полиномов G(X) бином X

+1 рас-

кладывается на три неприводимых полинома

+ 1 = (X + 1)·(X

+ X

+ 1)·(X

+ X+ 1) = G

(X) × G

(X), (4.11)

каждый из которых является порождающим для следующих кодов:

(X) =

+ 1

- код с проверкой на чётность, КПЧ (7, 6);

(X) = X

+ X

+ 1 - первый вариант кода Хемминга (7,4);

(X) = X

+ X+ 1 - двойственный G

(X), второй вариант кода Хемминга.

Кроме того, различные вариации произведений G

(X) дают возможность полу-

чить остальные порождающие полиномы:

(X) = G

(X)·G

(X) = (X + 1)·(X

+ X

+ 1) = X

+ X

+ X +1 -

код Абрамсона (7,3);

(X) = G

(X)·G

(X) = (X + 1)·(X

+ X+ 1) = X

+ X

+1 -

двойственный G

(X);

(X) = G

(X)·G

(X) = (X

+ X

+ 1)·(X

+ X+ 1) =

= X

+ X

+ X +1 - код с повторением (7,1).

Таким образом, для постоянного заданного значения n все возможные порож-

дающие полиномы ЦК размещаются между кодами с проверкой на чётность (n, n-1)

(r =1) и кодами с повторением (n, 1) (r = n -1), которые правомерно и называют "кодами

антиподами".

При выборе применяемых в системах связи корректирующих кодов необходимо

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

носительная скорость кода или эффективность кода была максимальной, а, во-

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

1.4. Принципы формирования и обработки разрешённых

кодовых комбинаций циклических кодов

На основании материалов предыдущего раздела можно дать следующее опреде-

ление циклических кодов.

Циклические коды (ЦК) составляют множество многочленов Вi(Х) степени n -1 и

менее (до r = n - k, где r - число проверочных символов), кратных порождающему (обра-

зующему) полиному G(Х) степени r, который, в свою очередь, должен быть делителем

бинома X

+ 1, т. е. остаток после деления бинома на G(X) должен равняться нулю.

Учитывая,что ЦК принадлежат к классу линейных, групповых кодов, сформулиру-

ем ряд основных свойств, им присущих.

1. Сумма разрешённых кодовых комбинаций ЦК образует разрешённую кодовую

комбинацию

(X) ⊕ B

(X) = B

(X). (4.12)

2. Поскольку к числу разрешённых кодовых комбинаций ЦК относится нулевая

комбинация 000...00, то минимальное кодовое расстояние d

min

для ЦК определяется ми-

нимальным весом разрешённой кодовой комбинации:

min

= W

min

. (4.13)

3. Циклический код не обнаруживает только такие искажённые помехами кодо-

вые комбинации, которые приводят к появлению на стороне приёма других разрешённых

комбинаций этого кода из набора Ν

4. Значения проверочных элементов r = n - k для ЦК могут определяться путём

суммирования по модулю 2 ряда определённых информационных символов кодовой

комбинации А

(Х). Например, для кода Хемминга (7,4) с порождающим полиномом

G(X)=X

+Х+1 алгоритм получения проверочных символов будет следующим [3]:

= i

⊕ i

;

= i

⊕ i

; (4.14)

= i

⊕ i

;

Эта процедура свидетельствует о возможности "поэлементного" получения прове-

рочной группы для каждой кодовой комбинации А

(Х). В соответствии с (4.14) могут стро-

иться кодирующие устройства для ЦК [3].