Помехоустойчивые циклические коды: Учебное пособие

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

Санкт-Петербургский государственный университет аэрокосмического приборостроения Г. И. Никитин

ПОМЕХОУСТОЙЧИВЫЕ ЦИКЛИЧЕСКИЕ КОДЫ

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

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

2

Никитин Г. И.

Помехоустойчивые циклические коды: Учеб. пособие/СПбГУАП. В пособии даётся классификация разновидностей, характеристик и параметров корректирующих кодов, изложены принципы построения, формирования и обработки помехоустойчивых циклических кодов, их определение, свойства и эффективность, а также реализация кодирующих и декодирующих устройств этих кодов на базе линейных переключательных схем. Приводятся примеры применения циклических кодов и линейных переключательных схем в радиотехнических системах, в том числе в космических системах передачи информации. Рассмотрен порядок выполнения лабораторной работы " Циклические коды". Пособие предназначено для студентов, изучающих специальность "Радиотехника".

3 Список основных сокращений АКФ - автокорреляционная функция АРБ - аварийный радиобуй АТС - автоматическая телефонная станция БРК - бортовой радиокомплекс ВКФ - взаимнокорреляционная функция ДУ - декодирующее устройство ЗНД - защита от несанкционированного доступа ЗУ - запоминающее устройство ИКАО - Международная организация гражданской авиации ИМО - Международная морская организация ИС - источник сообщений ИСЗ - искусственный спутник Земли ИЦСС - интегрально-цифровые системы связи КЭАТС - квазиэлектронные АТС КУ - кодирующее устройство Коды: БЧХ РС ЦК НДК СДК КПВ КПЧ

- Боуза-Чоудхури-Хоквингема - Рида-Соломона - циклические коды - натуральный двоичный код - симметричный двоичный код - код с постоянным весом - код с проверкой на чётность

Л П С - линейная переключательная схема МККТТ - Международный консультативный комитет по телефонии и телеграфии ММП - метод максимального правдоподобия ОКС - общий канал сигнализации ОФМ - относительная фазовая модуляция ПС - получатель сообщений ПСП - псевдослучайная последовательность П П И - пункт приёма информации ППРЧ - программная перестройка рабочих частот СМД - синдромный метод декодирования СПД - система передачи данных СР - сдвигающий регистр ТИ - тактовый импульс ЦС - центр системы ЧВМ - частотно-временная матрица ЭМС - электромагнитная совместимость

4

Лабораторная работа № 4 “ИССЛЕДОВАНИЕ ЦИКЛИЧЕСКИХ И БЧХ-КОДОВ” ЦЕЛЬ РАБОТЫ: изучение принципов помехоустойчивого кодирования, ознакомление с циклическими и БЧХ-кодами, с методами кодирования и декодирования с использованием линейных переключательных схем на примере циклических кодов (15,k) и БЧХ-кода (15,7). ВВЕДЕНИЕ В настоящее время, в связи с многократно возросшими объёмами передаваемой и сохраняемой информации, ужесточились требования к её достоверности. Одним из самых перспективных методов решения этой проблемы является помехоустойчивое кодирование на основе корректирующих кодов. В последнее время коды, исправляющие ошибки, нашли применение во многих системах передачи и хранения информации. Наиболее известные из них – это сотовые системы связи, спутниковая спасательная система КОСПАС — САРСАТ, система глобальной морской связи ИНМАРСАТ, различные системы спутниковой телефонной связи, накопители информации на магнитных дисках, система звукозаписи на компакт-дисках и др. Во всех вышеприведённых примерах систем с помехозащищённой обработкой информации используются наиболее простые и эффективные циклические корректирующие коды, которые, наряду с простотой кодирования и декодирования, отличаются достаточно большой корректирующей способностью. Изучению этих кодов посвящена лабораторная работа. 1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ К ЛАБОРАТОРНОЙ РАБОТЕ Для выполнения лабораторной работы студенты должны предварительно изучить раздел 1 настоящего методического руководства и получить у преподавателя допуск к работе. 1.1. Классификация корректирующих кодов С классификацией корректирующих кодов студенты уже знакомы по материалам, приведённым в ЛР №3. В связи с этим напомним только основные положения, касающиеся циклических кодов. Все корректирующие коды можно разделить на два класса: блочные и непрерывные. Блочные коды — коды, в которых каждому сообщению (или элементу) сопоставляется блок из n символов (кодовый вектор длиной n). Операции кодирования и декодирования в каждом блоке производятся отдельно. Непрерывные коды представляют собой непрерывную последовательность символов, не подразделяемую на блоки. Такие коды называются также рекуррентными, цепными, свёрточными, конволюционными. Процессы кодирования и декодирования осуществляются непрерывно. Передаваемая последовательность образуется путём размещения в определённом порядке проверочных символов между информационными символами исходной последовательности. Как блочные, так и непрерывные коды делятся на разделимые и неразделимые.

5 Разделимые коды предусматривают возможность чёткого разграничения информационных и проверочных символов. Неразделимые коды не предусматривают такой возможности и к ним относятся, например, коды с постоянным весом (КПВ). Разделимые коды делятся, в свою очередь, на систематические (линейные или групповые) и несистематические (нелинейные). Систематические коды характеризуются тем, что сумма по модулю 2 двух разрешённых кодовых комбинаций кодов этого класса снова даёт разрешённую кодовую комбинацию. Кроме того, в систематических кодах информационные символы, как правило, не изменяются при кодировании и занимают определённые заранее заданные места. Проверочные символы вычисляются как линейная комбинация информационных, откуда и возникло другое наименование этих кодов — линейные. Для систематических кодов принимается обозначение [n, k] - код, где k — число информационных символов в кодовой комбинации, n — общее число символов в коде. Несистематические коды не обладают отмеченными выше свойствами и применяются значительно реже, чем систематические, в частности, в несимметричных каналах связи. К этому классу кодов относятся такие, например, коды как КПВ, итеративные, комбинационные и антифединговые [3]. Циклические коды составляют большую группу наиболее широко используемых на практике линейных, систематических кодов. Их основное свойство, давшее им название, состоит в том, что каждый вектор, получаемый из исходного кодового вектора путём циклической перестановки его символов, также является разрешённым кодовым вектором. Принято описывать циклические коды (ЦК) при помощи порождающих полиномов G(Х) степени r = n — k, где r — число проверочных символов в кодовом слове. В связи с этим ЦК относятся к разновидности полиномиальных кодов. Операции кодирования и декодирования ЦК сводятся к известным процедурам умножения и деления полиномов. Для двоичных кодов эти операции легко реализуются технически с помощью линейных переключательных схем (ЛПС), при этом получаются относительно простые схемы кодеков, в чём состоит одно из практических достоинств ЦК. Среди циклических кодов особое место занимает класс кодов, предложенных Боузом и Чоудхури и независимо от них Хоквингемом. Коды Боуза—ЧоудхуриХоквингема получили сокращённое наименование БЧХ- коды. БЧХ- коды являются обобщением кодов Хемминга на случай исправления нескольких независимых ошибок (gи >1). Частными случаями БЧХ- кодов являются коды Файра, предназначенные для обнаружения и исправления серийных ошибок ("пачек" ошибок), код Голея - код, исправляющий одиночные, двойные и тройные ошибки (dmin=7), коды Рида-Соломона (РС- коды), у которых символами кода являются многоразрядные двоичные числа. 1.2. Полиномиальное определение циклических кодов и операции с ними Циклические коды являются частным случаем систематических, линейных [n, k]кодов. Название ЦК получили из-за своего основного свойства: циклическая перестановка символов разрешённой кодовой комбинации даёт также разрешённую кодовую комбинацию. При циклической перестановке символы кодового слова перемещаются слева направо на одну позицию, причем крайний справа символ переносится на место крайнего левого. Если, например, А1 - 101100, то разрешённой кодовой комбинацией будет и А2 - 010110, полученная циклической перестановкой. Отметим, что перестановка производится вместе с проверочными символами, и по правилам линейных кодов сумма

6 по модулю 2 двух разрешённых кодовых комбинаций даёт также очередную разрешённую кодовую комбинацию. Описание ЦК связано с представлением кодовых комбинаций в виде полиномов (многочленов) фиктивной переменной "X". Для примера переведём кодовое слово А1 = 101100 в полиномиальный вид

i код

6 1

5 0

4 1

3 1

2 0

1 0

При этом А1(X) = 1 · X5 + 0 · X4 + 1 · X3 + 1 · X2 + 0 · X1 + 0 · X0 = X5 + X3 + X2. Действия с кодовыми векторами, представленными в виде полиномов, производятся по правилам арифметики по модулю 2, в которой вычитание равносильно сложению. Так, из равенства Хn -1 = 0 получаем Хn =1. Прибавив к левой и правой частям по единице, имеем Хn + 1 = 1 ⊕ 1= 0. Таким образом, вместо двучлена Хn -1 можно ввести бином Хn +1 или 1 + Хn , из чего следует, что Хk ⊕ Хk = Хk (1 ⊕ 1) = 0 и при последующих операциях с полиномами необходимо вычёркивать пары фиктивных переменных X с одинаковыми степенями. Приведём далее порядок суммирования (вычитания), умножения и деления полиномов с учётом того, что операция суммирования осуществляется по модулю 2. В примерах используем вышеприведённые кодовые комбинации А1(X) = X5 + X3 + X2 и А2(X) = X4 + X2+ X. Суммирование (вычитание): А1 + А2 = А1 - А2 = X5 + X4 + X3 + X2 + X2+ X = X5 + X4 + X3+ X или

А1 А2

101100 ⊕ 010110 _______ 111010 = X5 + X4 + X3+ X.

Умножение: А1 × А2 = ( X5 + X3 + X2 ) × ( X4 + X2+ X) = X9 + X7 + X6+ X7 + X5 + + X4 + X6 + X4 + X3= X9 + X5 + X3 = 1000101000. Деление:

A1 A

X5 + X3 + X2 │ X4 + X2+ X │—————— X5 + X3 + X2 X —————— 0 0 0 - остаток при делении R(X) = 0. Из последнего примера следует, что при циклическом сдвиге вправо на один разряд необходимо исходную кодовую комбинацию поделить на X, а умножение на X эквивалентно сдвигу влево на один символ. На основании того, что будет сказано далее о ЦК, нельзя установить теоретически те или иные свойства этих кодов, ряд приводимых ниже результатов придётся принять без соответствующих доказательств на веру. Однако, рассмотрев приведённые далее примеры, можно понять и освоить специфику и идеологию формирования и обработки ЦК.

7 1.3. Порождающие полиномы циклических кодов Формирование разрешённых кодовых комбинаций ЦК Bi (X) основано на предварительном выборе так называемого порождающего (образующего) полинома G(X), который обладает важным отличительным признаком: все комбинации Bi (X) делятся на порождающий полином G(X) без остатка, т. е. Bi ( X ) = Ai ( X ) ( при остатке R( X ) = 0 ), G( X )

(4.1)

где Аi(Х) — информативный полином (кодовая комбинация первичного кода, преобразуемого в корректирующий ЦК). Поскольку, как отмечалось выше, ЦК относятся к классу блочных разделимых кодов, у которых при общем числе символов n число информационных символов в Аi(Х) равно k, то степень порождающего полинома определяет число проверочных символов r = n - k. Из этого свойства следует сравнительно простой способ формирования разрешённых кодовых комбинаций ЦК — умножение комбинаций информационного кода Аi(Х) на порождающий полином G(X): Bi (X) = Ai (X)·G(X). (4.2) В теории циклических кодов доказывается, что порождающими могут быть только такие полиномы, которые являются делителями двучлена (бинома) Xn+1: X n +1 = H ( X ) ( при остатке R( X ) = 0 ). (4.3) G( X ) Возможные порождающие полиномы, найденные с помощью ЭВМ, сведены в обширные таблицы. Так, в [6] приведены таблицы G(X) с записью полиномов в восьмеричной системе счисления (mod 8). В этом случае весовые коэффициенты ki представляют три двоичных знака в соответствии со следующим кодом: 0 - 000 2 - 010 4 - 100 6 - 110  (4.4) 1 - 001 3 - 011 5 - 101 7 - 111  Двоичные символы являются весовыми коэффициентами порождающих полиномов, коэффициенты восьмеричной системы счисления расположены слева от них с учётом того, что 0 ≤ ki ≤ 7 (при mod 8). Например, 3425 обозначает многочлен 10-й степени, В двоичной записи числу 3425 (mod 8) эквивалентно число 011100010101 и соответствующий многочлен равен X10 + X9 + X8 + X4 + X2 + 1. Как видно из этого примера, восьмеричная система счисления для записи многочленов выбрана, в частности, из соображений экономии длины записи (бумаги) в три раза при больших объёмах табулированных значений, что подчёркивает известный недостаток двоичной системы счисления. Некоторые из порождающих полиномов приведены в табл. 1. Следует отметить, что с увеличением максимальной степени порождающих полиномов r резко увеличивается их количество. Так, при r = 3 имеется всего два полинома, а при r = 10 их уже несколько десятков. Первый порождающий полином минимальной степени r=1, удовлетворяющий условию (4.3), формирует код с проверкой на чётность при двух информативных символах и одном проверочном, обеспечивающем обнаружение однократной ошибки, поскольку минимальное кодовое расстояние dmin= 2. В общем случае коэффициент избыточности КПЧ минимален: r 1 κ= = , (4.5) n n а относительная скорость кода – максимальна и равна

8 k n −1 Bk = = , n n

(4.6)

В связи с этим КПЧ иногда называют быстрым кодом. Таблица 1 r-степень Порождаю- Запись поли- Запись полиполинома щий полином нома по mod 2 нома по mod 8 G(X) G(X) 1

X+1

2 3

X2+X+1 X3+X2+1 X3+X+1 X4+X3+1 X4+ X+1 X4+X2+X+1 X4+X3+X2+1 X5+X2+1 X5+X3+1 ... ... X6+X5+X4+ +X3+X2+X1+1 ... ...

4

5

6

n

k

Примечание Код с проверкой на чётность (КПЧ) Код с повторением Классический код Хемминга Классический код Хемминга Коды ФайраАбрамсона

11

3

3

2

111 1101 1011 11001 10011 10111 11101 100101 101001

7 13 15 31 23 27 35 45 51

3 7 7 15 15 7 7 31 31

1 4 4 11 11 3 3 26 26

1111111

177

7

1

Классический Хемминга

код

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

Второй порождающий полином степени r =2, являющийся "партнёром" первого G(X) = X+ 1 при разложении бинома с n = 3, определяет код с повторением единственного информативного символа k =1 ("0" или "1"). Отметим, что ЦК принадлежат к классу линейных кодов, у которых кодовые комбинации "000 ... 00" и "111... 11 " являются разрешёнными. У кода с повторением возможности обнаружения и исправления ошибок безграничны, поскольку число повторений ℓ [1] определяет минимальное кодовое расстояние: d min = ℓ. (4.7) В общем случае коэффициент избыточности кодов с повторением кодовых комбинаций является максимально возможным: nl − n l − 1 1 κ= = =1 − , nl l l и при увеличении ℓ приближается к 1, а скорость (4.6) - минимальна 1 Bk = 1 − κ = . l

(4.8)

Таким образом, коды с проверкой на чётность и коды с повторением - до некоторой степени антиподы. Первый код очень быстр (всего один дополнительный символ), но зачастую "легкомыслен". Возможности второго кода с повторением по исправлению ошибок теоретически безграничны, но он крайне "медлителен" [7]. Следующие порождающие полиномы в табл. 1 со степенью r = 3 позволяют сформировать набор классических корректирующих кодов Хемминга (7, 4), которые исследовались студентами ранее при выполнении лабораторной работы N3 "Корректирующие коды". Коды Хемминга также принадлежат к классу ЦК, однако при этом гpyппa

9 проверочных символов кода получается сразу "в целом" при делении информативной кодовой группы на порождающий полином, а не "поэлементно", как это показано в ЛР №3, когда последовательное суммирование по модулю 2 соответствующих информативных символов давало очередной символ проверочной группы. Отметим, что два варианта порождающих полиномов кода Хемминга (7,4), с записью по модулю 2 в виде 1101 и 1011, представляют собой так называемые двойственные многочлены (полиномы). Двойственные многочлены определяются следующим образом: если задан полином в виде h(X) = h0 +h1X + h2X2 + … + hrXr, то двойственным к нему полиномом является ~ h (X) = h 0 X r + h 1X r −1 + ... + h r ,

(4.9)

т. е. весовые коэффициенты исходного полинома, зачитываемые слева направо, становятся весовыми коэффициентами двойственного полинома при считывании их справа налево. Говоря образно, набор весовых коэффициентов "вывёртывается наизнанку". Обратим внимание на то, что в полных таблицах порождающих ЦК полиномов двойственные полиномы, как правило, не приводятся [6]. Наряду с тем, что порождающие полиномы кода Хемминга (7,4) являются двойственными друг другу, они также являются неприводимыми. Неприводимые полиномы не делятся ни на какой другой полином степени меньше r, поэтому их называют ещё неразложимыми, простыми и примитивными. Далее в табл. 1 при значениях r = 4 и 5 попадают следующие классические коды Хемминга (15, 11) и (31, 26). Порождающие их полиномы также являются двойственными друг к другу и неприводимыми. Напомним, что к классическим кодам Хемминга относятся коды, у которых n = 2 r- 1, a k = 2 r -1- r [3], с минимальным кодовым расстоянием dmin= 3, позволяющим исправлять однократные ошибки и обнаруживать двойные. При значениях r = 4 в табл. 1 попадают двойственные порождающие многочлены кода Абрамсона (7, 3), являющиеся частным случаем кодов Файра, порождающие полиномы для которых имеют вид G(X) = p(X) · (Xc + 1),

(4.10)

где р(Х) - неприводимый полином. Коды Абрамсона совпадают с кодами Файра, если положить с = 1. Число проверочных символов r = 4 определяет общее число символов в коде (значность кода), поскольку для этих кодов n = 2 r-1- 1. Эти коды исправляют все одиночные и смежные двойные ошибки (т.е. серии длиной 2). Помещённые в табл. 1 коды Абрамсона (7,3) являются первыми циклическими кодами, исправляющими серийные ошибки (пакеты ошибок). В этом применении ЦК оказываются особенно эффективными. Обратим внимание на то, что при с =1 в (4.10) порождающими полиномами р(X) являются двойственные полиномы X3 + X2+ 1 и X3 + X+ 1, образующие код Хемминга (7, 4) при r = 3. Серийные ошибки возникают в результате воздействия в канале передачи сообщений помех импульсного характера, длительность которых больше длительности одного символа. При этих условиях ошибки уже не независимы, а возникают пачками, общая длительность которых соответствует длительности помехи. В заключение на основании данных табл. 1 приведём все возможные порождающие полиномы для кодовых комбинаций с числом символов n = 7. В соответствии со свойством (4.3) порождающих полиномов G(X) бином X7 +1 раскладывается на три неприводимых полинома X7 + 1 = (X + 1)·(X3 + X2+ 1)·(X3 + X+ 1) = G1 (X) × G2 (X) × G3 (X), каждый из которых является порождающим для следующих кодов:

(4.11)

10 - код с проверкой на чётность, КПЧ (7, 6); G1 (X) = Х+ 1 3 2 G2 (X) = X + X + 1 - первый вариант кода Хемминга (7,4); ~ G3 (X) = X3 + X+ 1 - двойственный G 2 (X), второй вариант кода Хемминга. Кроме того, различные вариации произведений G1,2, 3(X) дают возможность получить остальные порождающие полиномы: G4 (X) = G1 (X)·G2 (X) = (X + 1)·(X3 + X2+ 1) = X4 + X2+ X +1 код Абрамсона (7,3); G5 (X) = G1 (X)·G3 (X) = (X + 1)·(X3 + X+ 1) = X4 + X3+ X2 +1 двойственный G4 (X); G6 (X) = G2 (X)·G3 (X) = (X3 + X2+ 1)·(X3 + X+ 1) = = X6 + X5 +X4 + X3 + X2+ 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 n + 1, т. е. остаток после деления бинома на G(X) должен равняться нулю. Учитывая,что ЦК принадлежат к классу линейных, групповых кодов, сформулируем ряд основных свойств, им присущих. 1. Сумма разрешённых кодовых комбинаций ЦК образует разрешённую кодовую комбинацию (4.12) Bi(X) ⊕ Bj(X) = Bk(X). 2. Поскольку к числу разрешённых кодовых комбинаций ЦК относится нулевая комбинация 000...00, то минимальное кодовое расстояние dmin для ЦК определяется минимальным весом разрешённой кодовой комбинации: Dmin = Wmin. (4.13) 3. Циклический код не обнаруживает только такие искажённые помехами кодовые комбинации, которые приводят к появлению на стороне приёма других разрешённых комбинаций этого кода из набора Ν0. 4. Значения проверочных элементов r = n - k для ЦК могут определяться путём суммирования по модулю 2 ряда определённых информационных символов кодовой комбинации Аi(Х). Например, для кода Хемминга (7,4) с порождающим полиномом G(X)=X3+Х+1 алгоритм получения проверочных символов будет следующим [3]: r1 = i1 ⊕ i2 ⊕ i3 ; r2 = i2 ⊕ i3 ⊕ i4 ; (4.14) r3 = i1 ⊕ i2 ⊕ i4 ; Эта процедура свидетельствует о возможности "поэлементного" получения проверочной группы для каждой кодовой комбинации Аi(Х). В соответствии с (4.14) могут строиться кодирующие устройства для ЦК [3].

11 5. Как было показано на примере в подразделе 1.2, умножение полинома на X приводит к сдвигу членов полинома на один разряд влево, а при умножении на Xr , соответственно, на r разрядов влево, с заменой r младших разрядов полинома "нулями". Умножение полинома на X свидетельствует о том, что при этой процедуре X является "оператором сдвига". Деление полинома на X приводит к соответствующему сдвигу членов полинома вправо с уменьшением показателей членов на 1. Процедура сдвига позволяет к исходной кодовой комбинации Аi(Х), после домножения её на Xr, дописать справа r проверочных символов. 6. Поскольку разрешённые кодовые слова ЦК Bi(X) без остатка делятся на порождающий полином G(X) с получением итога в виде информационной комбинации Аi(Х) (4.1), то имеется возможность формировать Bi(X) на стороне передачи (кодирующее устройство) простым методом умножения (4.2). Два последних свойства ЦК позволяют осуществить построение кодеров ЦК двумя методами: методом умножения и методом деления полиномов. Рассмотрим достоинства и недостатки этих методов с учётом вариантов построения декодеров ЦК, соответствующих этим методам. Метод умножения позволяет при формировании разрешённых кодовых комбинаций по алгоритму (4.2) использовать любой порождающий полином, лишь бы его максимальная степень была равна числу необходимых проверочных символов r. Однако этот метод обладает двумя существенными недостатками. Во-первых, при формировании ЦК методом умножения в полученной комбинации Bi(X) в явном виде не содержатся информационные символы. Код получается неразделимым с "перетасованными" информативными и проверочными символами, что затрудняет его декодирование, так как это приводит к необходимости применять метод максимального правдоподобия в декодирующем устройстве (ДУ). Метод максимального правдоподобия (ММП) предполагает при исправлении ошибок принимаемую кодовую комбинацию отождествлять с той разрешённой, к которой принятая находится ближе всего. При таком непосредственном способе декодирования в памяти запоминающего устройства (ЗУ) декодера необходимо хранить все разрешённые кодовые комбинации N0, что требует на стороне приёма больших объёмов ЗУ и большого времени обработки при декодировании. Эти обстоятельства являются вторым недостатком метода умножения при кодировании ЦК. Исследования показывают [5 - 8], что хороший циклический корректирующий код с кратностью исправляемых ошибок gu ≥ 5 при относительной скорости кода Вк ≥ 0,5, т. е. коэффициенте избыточности к ≤ 0,5, должен иметь число информационных символов k ≥ 40 . Это значение и приводит к техническим трудностям при процедуре декодирования по ММП, сводящейся к сравнению принятой кодовой комбинации со всеми N0 разрешёнными. Для примера определим время декодирования Тдк принятой кодовой комбинации, если число информационных символов в ней k= 40 и для сравнения используется ЭВМ со скоростью 107 операций в секунду. Будем полагать, что для сравнения принятой кодовой комбинации с одной из разрешённых достаточно одной операции на ЭВМ. Тогда для проведения N 0 = 2k = 240 сравнений потребуется время декодирования N 2 40 1,1 ⋅ 1012 1,1 ⋅ 10 5 5 T Дк = 0 = 7 = = 1 , 1 ⋅ 10 c = = 30 ч. VЭВМ 10 3600c 10 7 Как видно из примера, задача декодирования простым перебором и сравнением непосильна даже для современных ЭВМ. В соответствии с этим, основным направлением в теории кодирования является поиск таких кодов и алгоритмов их формирования и обработки, для которых не требуется хранение в ЗУ разрешённых кодовых комбинаций. Эти задачи решаются, в частности,

12 при построении кодеров на основе деления полиномов, а при декодировании — на основе синдромного метода декодирования (СМД). Метод деления полиномов позволяет представить разрешённые к передаче кодовые комбинации в виде разделённых информационных Ai(X) и проверочных Ri(X) символов, т. е. получить блочный код. Поскольку число проверочных символов равно r, то для компактной их записи в последние младшие разряды кодового слова надо предварительно к Ai(X) справа приписать r "нулей", что эквивалентно умножению Ai(X) на оператор сдвига X r (см. свойство 5 ЦК). На практике предпочитают использование метода деления полиномов при построении кодеков, поскольку при этом имеется возможность представить кодовую комбинацию в виде разделённых информационных и проверочных символов: Bi (X) = Ai (X) ·Xr + Ri (X), (4.15) где Ri (X) — остаток от деления Ai (X) ·Xr /G(X). В алгоритме (4.15) можно выделить три этапа формирования разрешённых кодовых комбинаций в кодирующем устройстве: 1) к комбинации первичного кода Ai(X) дописывается справа r нулей, что эквивалентно умножению Ai (X) на Xr ; 2) произведение Ai(X)·Xr делится на соответствующий порождающий полином G(X) и определяется остаток Ri(X), степень которого не превышает r - 1, этот остаток и даёт группу проверочных символов; 3) вычисленный остаток присоединяется справа к Ai (X) ·Xr. Пример 1. Рассмотрим процедуру кодирования по алгоритму (4.15): для кодовой комбинации А=1001 сформировать кодовую комбинацию циклического кода (7,4). В заданном ЦК n = 7, k = 4, r = 3, и из табл. 1 выберем порождающий полином G(X) = X3 + X + 1 (код Хемминга). Выполним три необходимые операции для получения кодовой комбинации ЦК согласно алгоритму (4.15): Ai (X) = 1001 ~ X3 + 1 , ( знак " ~ " – тильда – означает соответствие). 1. Ai (X) ·Xr = (X3 + 1 ) · X3 = X6 + X3 ~1001000, ( n =7). 2. Ai (X) ·Xr /G(X) = X6 + X3 │ X3 + X + 1 + │—————— X6 + X4 + X3 X3 + X —————— X4 + X4 + X2+ X —————— X2+ X - остаток Ri (X) = X2 + X ~ 110. 3. Bi (X) = Ai (X) ·Xr + Ri (X) = 1001110 - итоговая комбинация ЦК. Синдромный метод декодирования (СМД) предполагает в ДУ принятую кодовую комбинацию поделить на порождающий полином. Если принятая комбинация является разрешённой, т. е. не искажена помехами в канале связи, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о наличии в принятой кодовой комбинации ошибок, остаток от деления и называется синдромом. Термин "синдром" заимствован из медицинской практики (от греч. вместе бегущий) и означает сочетание (комплекс) симптомов болезни, характерное для определённого заболевания. В теории кодирования синдром, который также называют опознавателем ошибки, обозначает совокупность признаков, характерных для определённой ошибки. Для исправления ошибки на стороне приёма необходимо знать не только факт

13 её существования, но и её местонахождение, которое определяется по установленному виду вектора ошибки z(X). После передачи по каналу с помехами принимается кодовое слово Bi' (X) = Bi(X) + z(X), (4.16) где Bi(X) - передаваемая кодовая комбинация; z(X) — полином (вектор) ошибки, имеющий степень от 1 до n -1. При декодировании принятое кодовое слово делится на G(X) Bi′( X ) = U i ( X ) + Si ( X ) , G( X )

(4.17)

где остаток от деления Si(X) и является синдромом. Если при делении получается нулевой остаток Si(X) = 0, то выносится решение об отсутствии ошибки z(X) = 0. Если остаток (синдром) ненулевой Si(X)≠ 0, то выносится решение о наличии ошибки и определяется шумовой вектор (полином) z(X), а затем передаваемое кодовое слово, поскольку из (4.16) следует Bi(X) = Bi' (X) + z(X). (4.18) Всякому ненулевому синдрому соответствует определённое расположение (конфигурация) ошибок. Взаимосвязь между видом синдрома и местоположением ошибочного символа находится довольно просто. Достаточно в любую разрешённую кодовую комбинацию ввести ошибку и выполнить деление на G(X). Полученный остаток (4.17) - синдром и будет указывать на ошибку в этом символе. В качестве примера для ЦК Хемминга (7,4), позволяющего исправлять однократную ошибку при dmin = 3 (см. табл. 1), взаимосвязь между синдромом и ошибочным символом для двух возможных порождающих полиномов кода (7,4) приведена в табл. 2. Пользуясь этой таблицей, можно найти местоположение ошибки и исправить её. Для параметров рассмотренного ранее примера 1, где была показана процедура кодирования кодовой комбинации Ai = 1001 при использовании порождающего полинома G(X) = X3 + X +1 для кода Хемминга (7,4), исправляющего однократную ошибку, приведём в примере 2 процедуру декодирования принятой с помехой кодовой комбинации. Пример 2. Принятая кодовая комбинация ЦК (7,4) имеет Bi'(X)=1011110. Определить и исправить ошибку в Bi' (X), если она имеется. Выполним три необходимые операции, проводимые при декодировании: Таблица 2 № символа комбинации со старшего разряда 7 6 5 4 3 2 1

Ошибочный символ полинома комбинации X6 X5 X4 X3 X2 X1 X0

Синдром для порождающего полинома G(X)=X3+X+1 101 111 110 011 = H к (7,4) 100 010 001 см. 4.29

Нет ошибки

000

Синдром для порождающего полинома G(X)=X3+X2+1 110 011 111 ~ 101 = H к (7,4) 100 010 001

Шумовой вектор z(X) 1000000 0100000 0010000 0001000 0000100 0000010 0000001

см. 4.29 000

1) в соответствии с алгоритмом (4.17) производим деление

0000000

вид

14 Bi' (X) / G(X) = X6 + X4 + X3 + X2 + X │ X3 + X +1 │—————— X6 + X4 + X3 X3 ————————— X2 + X - остаток R(X) = X2 + X ~ 110, отметим, что совпадение остатков в примере 1 и 2 — чисто случайное, в примере 1 остаток являлся проверочной группой кода, а в примере 2 - синдромом; 2) по полученному синдрому 110 в соответствующем опознавателе синдрома (дешифраторе синдрома, локаторе ошибки) определяем вид шумового вектора z(X) 0010000 (см. табл. 2); 3) воспользовавшись алгоритмом (4.18), исправляем принятую кодовую комбинацию Bi' (X) и получаем переданную комбинацию Bi (X): Bi (X) = Bi' (X) + z(X) = 1011110 + 0010000 ———— 1001110 – исправленная комбинация на выходе ДУ с инвертированием неверно принятого символа. Число проверочных символов r = n - k определяет число исправляемых ошибок. Значение r должно быть достаточным для получения необходимого числа синдромов SΣ (опознавателей ошибок). Так, для исправления всех одиночных (однократных) ошибок необходимо SΣ = n +1 синдромов, так как шумовой вектор может принимать следующие n значений: 000...01, 000...10, ..., 001...00, 010...00, 100...00, кроме того, необходим один синдром для определения факта безошибочного приёма кодовой комбинации S0 = 000...00. Таким образом, для двоичных кодов при необходимости исправления всех однократных ошибок требуется выполнение соотношения (4.19) SΣ = 2 n – k = 2 r = n +1 , поскольку синдром формируется на месте r проверочных разрядов кода. Плотноупакованные коды — такое название получили коды, у которых соблюдается точное равенство В (4.19) числа необходимых синдромов для исправления ошибок заданной кратности. Вследствие уникальности таких кодов, плотноупакованные коды называют также "совершенными" или "оптимальными". К таким кодам относятся коды Хемминга, которые при минимальном кодовом расстоянии dmin = 3 обеспечивают исправление всех однократных ошибок, поскольку у классических кодов Хемминга число символов n = 2 r -1 удовлетворяет условию (4.19). В общем случае, при необходимости исправления всех независимых ошибок кратности до gи включительно, требуемое число синдромов определяется выражением S Σ =1 + C n1

+ C n2

+ C n3

+ ... + C ngи

gи

= ∑ C ni ,

(4.20)

i =0

n! - число сочетаний из n по i, причём C 0n =1 , так как 0! = 1. (n − i )!⋅ i! С учётом (4.19) и (4.20), можно получить выражение для оценки числа проверочных символов r при необходимости исправления gи - кратных ошибок в принятых кодовых комбинациях где C ni =

 gи  r ≥ log 2  ∑ C ni  .    i =0 

(4.21)

15 Занимаясь поиском плотноупакованных кодов ("кодов без потерь"), М. Голей заметил (опубликовано в 1949 году), что 0 1 2 3 + C 23 + C 23 + C 23 =1 + 23 + 253 + 1771 = 211 , C 23

а это означало, что может существовать плотноупакованный двоичный (23,12) код, удовлетворяющий условию (4.20), исправляющий все кодовые комбинации с тремя или менее ошибками. Он показал, что такой код действительно существует и в дальнейшем этот код получил его имя. Код Голея относится к классу ЦК с порождающими двойственными (дуальными) полиномами (4.9): G( X ) = X 11 + X 10 + X 6 + X 5 + X 4 + X 2 + 1 ; (4.22) ~ G( X ) = X 11 + X 9 + X 7 + X 6 + X 5 + X + 1 . Простым вычислением проверяется, что ~ X 23 + 1 = (X + 1) ⋅ G (X) ⋅ G (X) , в связи с чем в качестве порождающего полинома ЦК Голея (23, 12) можно использовать как G(X), так и G̃(X). Код Голея, гарантированно исправляющий ошибки с кратностью не менее трёх включительно, обладает минимальным кодовым расстоянием, dmin =2g и +1 = 7, что, как правило, указывается в маркировке кода (23, 12, 7). Добавление к этому коду общей проверки на чётность по всем позициям увеличивает на единицу как общую длину кода, так и минимальное кодовое расстояние dmin = 8. Расширенный код Голея, имеющий маркировку (24, 12, 8), состоит из 12 информационных символов и 12 проверочных, т. е. представляет собой код, обладающий скоростью 1/2 и избыточностью, также равной 1/2. Обратим внимание на то, что плотноупакованные коды Хемминга и Голея — циклические, которые принадлежат классу двоичных линейных кодов. Общим для линейных двоичных кодов является наличие, в качестве разрешённого, нулевого кодового слова 000...00, что приводит к тому, что минимальный вес wmin ненулевого разрешённого кодового слова равен минимальному кодовому расстоянию dmin (4.13). В общем случае вес кодовых комбинаций может принимать различные значения, и совокупность чисел кодовых комбинаций с постоянным весом Nw определяют как распределение весов кода или как спектр весов кода. Распределение весов в коде Голея (23, 12, 7) следующее: N0 = N23 = 1; N7 = N16 = 253; N8 = N15 = 506; N11 = N12 = 1288, а в расширенном коде Голея N0 = N24 = 1;

N8 = N16 = 759;

N12 = 2576.

(4.23)

Кодовые слова с весом 12, 8 и 16, выделенные из кода (24,12,8). образуют КПВ максимальной мощности. К сожалению, кроме кодов Хемминга (dmin = 3, gи =1) и кода Голея (23, 12, 7) пока не найдено других совершенных, плотноупакованных кодов, число синдромов у которых точно соответствует требуемому значению для гарантированного исправления ошибок заданной кратности. 1.5. Построение порождающих и проверочных матриц циклических кодов Наряду с полиномиальным способом задания кода, структуру построения кода можно определить с помощью матричного представления. При этом в ряде случаев проще реализуется построение кодирующих и декодирующих устройств ЦК.

16 Рассмотрим варианты формирования и обработки ЦК, заданных в виде порождающих и проверочных матриц, на конкретном примере ЦК Хемминга (7, 4), воспользовавшись выражением (4.11), в котором определены двойственные (дуальные) порождающие полиномы кода: X7+1 = (X +1) (X3+X+1) (X3+X2+1), что соответствует кодам (7, 6); (7, 4); (7, 4), Пример 3. Задан ЦК (7,4) дуальными порождающими полиномами ~ G(7,4) = X3+X+1 и G( 7 ,4 ) = X 3 + X 2 + 1. Составить порождающие матрицы для формирования разрешённых кодовых комбинаций и проверочные матрицы для получения синдромов. Первой строкой в матрице записывается порождающий полином (в двоичном представлении) с домножением его на оператор сдвига Xr для резервирования места под запись r = 3 проверочных символов. Следующие k - 1 строк матриц получаются путём ~ последовательного циклического сдвига базового кодового слова матрицы G и G  на одну позицию вправо, поскольку при этом по определению ЦК также получаются разрешённые к передаче кодовые комбинации: 1011000 0101100 G( 7 ,4 ) = 0010110 0001011

1 2 3 4

1101000 ~ 0110100 G( 7 ,4 ) = 0011010 0001101

1 2 3 4

(4.24)

Однако в таком виде эти порождающие матрицы размерностью k×n -(n столбцов, k строк) могут образовать только неразделимый ЦК, т. е. код, у которого не определены жёстко места информационных и проверочных элементов. Для построения порождающей матрицы, формирующей разделимый блочный код, необходимо матрицу преобразовать к каноническому виду путём простых линейных операций над строками, промаркированными № 1- 4. С учётом свойства ЦК (4.12), каноническую форму матрицы можно получить путём сложения ряда разрешённых кодовых комбинаций. Каноническая матрица должна в левой части порождающей ЦК матрицы содержать единичную диагональную квадратную подматрицу порядка " k " для получения в итоге блочного ЦК. С этой целью для получения первой строки канонической матрицы GK(7,4) необходимо сложить по моду~ лю 2 строки с номерами 1, 3 и 4 матрицы G(7, 4), а для матрицы G k ( 7 ,4 ) — строки с ~ номерами 1, 2 и 3 матрицы G( 7 ,4 ) . В этом случае в матрицах (4.24) в первых строках остаются "1" только на первых позициях, а остальные "k-1" символов заменяются "0", что и соответствует первым строкам единичных подматриц порядка "k". Нормирование последующих трёх строк канонических матриц производится путём соответствующего суммирования строк матриц (4.24). В итоге имеем следующий вид дуальных канонических матриц: 1000 | 101 0100 | 111 Gk ( 7 ,4 ) = 0010 | 110 0001 { | 011 E

1 = 1⊕ 3 ⊕ 4 2 = 2⊕4 3=3 4=4 14243

№ строк G( 7 ,4 )

1000 | 110 0100 | 011 ~ Gk ( 7 ,4 ) = 0010 | 111 0001 { | 101 E

1=1⊕ 2 ⊕ 3 2= 2⊕3⊕ 4 3=3⊕4 4=4 14243

~ № строк G ( 7 ,4 )

(4.25)

17 Процесс кодирования первичных кодов на стороне источника сообщений сводится к умножению информационных посылок, представленных в виде векторов Āi(X), на соответствующую порождающую каноническую матрицу: Bi(X) = Āi(X) ·Gk. (4.26) Эта процедура позволяет получить блочные коды Хемминга "в целом", т, е. получить проверочную группу символов r1, r2, r3 сразу после выполнения операции (4.26). Наряду с этим имеется возможность формировать символы проверочной группы поэлементно, как это предусматривалось при выполнении студентами лабораторной работы № 3 "Корректирующие коды" [3], где 3 проверочных символа задавались следующими равенствами проверки на чётность: r1 = i1 ⊕ i2 ⊕ i3 ; r2 = i2 ⊕ i3 ⊕ i4 ; r3 = i1 ⊕ i2 ⊕ i4 ;

r1 = i1 ⊕ i3 ⊕ i4 ; r2 = i1 ⊕ i2 ⊕ i3 ; r3 = i2 ⊕ i3 ⊕ i4 .

(4.27)

Обратим внимание на то, что алгоритм (4.27) просто получается из рассмотрения порождающих коды Хемминга матриц (4.25), в которых проверочные подматрицы, содержащие 3 столбца (r1, r2, r3), имеют символы " 1" в тех строках, номера которых совпадают с маркировкой информационных символов i в равенствах (4.27) (см. (4.14)). При матричном варианте обработки принятых кодов на стороне получателя сообщений для получения синдрома необходимо принятую, возможно искажённую в канале, кодовую комбинацию Bi′ ( X ) умножить на проверочную матрицу Н(Х): S = Bi′ ( X ) ⋅ H ( X ) . (4.28) Процедура построения проверочной матрицы Н достаточно подробно рассмотрена в [3]. Заметим, что матрица Н с размерностью n х r может быть получена из порождающей матрицы канонического вида (4.25) путём дополнения проверочной подматрицы единичной матрицей размерности r х r, что даёт следующий вид дуальных проверочных матриц:

По определённому с помощью полученного синдрома (4.28) соответствующему шумовому вектору исправляются ошибки (4.18). Интересно отметить, что в табл. 2, в которой рассмотрена связь между синдромом и шумовым вектором для кода (7,4), колонки с синдромами дуальных порождающих полиномов полностью совпадают с (4.29). В ЦК Хемминга (n , k) все проверочные r = n - k разряды размещаются в конце кодовой комбинации и, как отмечалось, формируются "в целом". При поэлементном получении проверочных символов (4.27) целесообразно, чтобы каждый синдром представлял собой двоичное число, указывающее на номер разряда, в котором произошла ошибка. Коды, в которых синдромы (опознаватели) соответствуют указанному принципу, и предложил впервые Хемминг. В этом случае

18 для кода (7, 4) проверочные символы r1, r2, r3, (табл. 2) размещаются на первой, второй и четвертой позициях кодовой комбинации, отсчитываемых справа налево. Такое построение кодов упрощает декодирующее устройство на стороне получателя сообщений. 1.6. Укороченные циклические коды Поскольку ЦК порождаются делителями бинома Хn +1 (4.3), то для большей части значений n и k имеется относительно мало кодов, удовлетворяющих всем свойствам, присущим ЦК (см. подразд. 1.4). Поэтому естественно попытаться найти среди линейных кодов такие, которые хотя и не являются в действительности циклическими, обладают похожей математической структурой и столь же легко реализуются. При разработке систем передачи информации, работающих с дискретными сигналами в предположении необходимости исправления (обнаружения) ошибок, число информативных символов kΣ выбирают, как правило, таким, чтобы оно было кратным длине первичного кода k1: kΣ = а k1 , где а = 1, 2, 3, 4, …, а значение nΣ = kΣ + r, где число проверочных символов должно удовлетворять заданному значению кратности обнаруживаемых и исправляемых ошибок. В частности, ЭВМ обычно обмениваются машинными словами в виде байтов, состоящих из восьми символов (k1 = 8). При этом nΣ и kΣ часто не совпадают с табулированными в [6] ЦК. В этом случае по таблицам [6] находят ЦК, который соответствует обоснованному значению r=n-k для классического, табулированного ЦК, а затем уменьшают n и kΣ до n-ℓ и kΣ=k-ℓ, получая укороченный ЦК. Укороченные циклические коды (УЦК) получают из полных ЦК, используя для передачи информации только кодовые комбинации полного кода, содержащие слева ℓ нулей. Это даёт возможность построить УЦК (n-ℓ, k-ℓ) путём исключения первых ℓ столбцов и ℓ строк из порождающей матрицы (4.24). Полученный код не будет строго циклическим, так как циклический сдвиг не всегда будет приводить к получению очередной разрешённой кодовой комбинации. Поэтому укороченные (усечённые) ЦК часто называют псевдоциклическими или квазициклическими. Укороченные ЦК сохраняют основные свойства классических ЦК (см. подраздел 1.4), к числу которых относятся следующие: 1) УЦК образуются делителями бинома Хn+1 - порождающими полиномами G(X), такими же, как у полных ЦК; 2) УЦК относятся к классу линейных (групповых) кодов, для которых сумма разрешённых кодовых комбинаций УЦК также является разрешённой кодовой комбинацией (4.12); 3) УЦК обладает таким же минимальным (конструктивным) кодовым расстоянием как у исходного ЦК, и таким же числом проверочных символов (4.21), но не может быть плотноупакованным; 4) УЦК исправляет такое же число ошибок, что и ЦК, т.е. имеет такую же кратность обнаруживаемых и исправляемых ошибок; 5) при построении кодеков УЦК используются те же схемы, что и для классических ЦК, при условии, что каждому усечённому коду спереди приписывается ℓ нулей. Специфику построения УЦК рассмотрим на следующем примере. Пример 4. Передаче подлежит сообщение, закодированное стандартным кодом МТК-2 с числом информационных символов k = 5. Обеспечить у получателя сообщений исправление однократной ошибки в кодовом слове. Однократная ошибка исправляется при минимальном кодовом расстоянии dmin=3. Этому значению удовлетворяют коды Хемминга (7,4), (15,11), (31,26) ... (см. табл.1). Код (7,4) с числом информационных символов k= 4 не удовлетворяет ус-

19 ловию примера при необходимости передачи k = 5. Этому условию удовлетворяет следующий по порядку код Хемминга (15,11), если из общего числа символов n=15 и числа информативных символов k =11 вычесть одно и то же число ℓ= 6 (исключение первых ℓ столбцов и ℓ строк порождающей код матрицы с размерностью k × n). Получаем УЦК (9, 5), удовлетворяющий условию примера k = 5, dmin = 3, с числом проверочных символов r = 4. Для опорного ЦК (15,11) бином Xn +1 раскладывается на следующие неприводимые полиномы: X15 + 1 = (X + 1)·(X2 + X + 1) ·(X4 + X + 1) ·(X4 + X3 + 1) ·( X4 + X3 + X2 + X + 1), из которых для построения кода r = 4 можно выбрать любой из трёх последних. Выберем в качестве порождающего полинома G(X) = X4 + X+1 и на основе матрицы этого ЦК (15,11) покажем, как осуществляется отсечка: 

1 2  3 ℓ=6 4  5 ——— 6



7  8   9  10 11

Усечённая матрица (9,5) 10011 0000 010011000 G( 9,5 ) = 001001100 00010 0110 000010011

1 2 3 4 5

(4.30)

Приведём усечённую матрицу G(9,5) к каноническому виду путём соответствующего суммирования строк по аналогии с проводимыми преобразованиями с матрицами (4.24) и (4.25) и получим соответствующие равенства проверки на чётность при поэлементном формировании усечённого кода (9, 5) (см. (4.27) в качестве аналога):

10000| 0101 01000| 1011 Gk ( 9 ,5 ) = 00100| 1100 00010| 0110 00001 123 | 0011

1 = 1⊕ 4⊕ 5 2=2⊕5 3=3 4=4 5=5

r1 = i2 ⊕ i3 ; r2 = i1 ⊕ i3 ⊕ i4 ; r3 = i2 ⊕ i4 ⊕ i5 ; r4 = i1 ⊕ i2 ⊕ i5 .

(4.31)

E

Обратим внимание на то, что порождающая матрица УЦК GK(9, 5) и соответствующие ей алгоритмы проверки на чётность (4.31) полностью совпадают с выражениями (3.22) методических указаний, по которым студентами выполнялась лабораторная работа № 3. Таким образом, УЦК (9, 5) полностью удовлетворяет условиям примера 4.

20 1.7. Циклические коды Боуза –Чоудхури –Хоквингема Коды Боуза – Чоудхури - Хоквингема (БЧХ) представляют собой обширный класс кодов, способных исправлять несколько ошибок и занимающих заметное место в теории и практике кодирования. Интерес к кодам БЧХ определяется по меньшей мере тремя следующими обстоятельствами: 1) среди кодов БЧХ при небольших длинах существуют хорошие (но, как правило, не лучшие из известных) коды; 2) известны относительно простые и конструктивные методы их кодирования и декодирования; 3) полное понимание построения кодов БЧХ является наилучшей отправной точкой для изучения многих других классов кодов. Коды БЧХ независимо открыли Хоквингем (1959) и Боуз и Рой-Чоудхури (1960), которые доказали ряд теорем, устанавливающих существование таких ЦК, у которых минимизируется число проверочных символов, а также указывающих пути нахождения порождающих полиномов для этих кодов. Корректирующие свойства ЦК могут быть определены на основании следующей теоремы: для любых значений m и gи существует ЦК длиной n = 2m-1, исправляющий все ошибки кратности gи и менее (gи < m) и содержащий не более n – k ≤ mgи проверочных символов. Так, например, при n = 15, m= 4 и различных gи число проверочных символов будет равно: gи =1, n – k = m·gи = 4·1= 4; gи = 2, m·gи = 4·2 = 8; gи = 3, m·gи = 4·3 = 12. Соответствующие коды (n, k) будут (15,11), (15,7), (15,3). Напомним, что минимальное кодовое расстояние dmin = 2 · gи +1 и применительно к ЦК оно чаще называется конструктивным расстоянием. Если величины gи или d выбрать слишком большими, то получившийся в результате код будет тривиальным — в нём будет лишь один либо (при r > n) ни одного информационного символа. В табл. 3 даны параметры и порождающие полиномы некоторых кодов БЧХ. Полиномы приведены в восьмеричной форме записи, старшая степень расположена слева. Например, коду (15, 7) соответствуют двоичное представление 111010001 и многочлен G(X) = X8 + Х7 + Х6 + X4 +1. Подробные таблицы порождающих полиномов циклических кодов БЧХ приведены в [6]. Таблица 3 m 3 4

n 7 15

5

31

6

63

k 4 11 7 26 21 16 11 57 51 45 39 36

r 3 4 8 5 10 15 20 6 12 18 24 27

gи 1 1 2 1 2 3 5 1 2 3 4 5

G(X) – mod 8 13 23 721 45 3551 107657 5423325 103 12471 1701317 166623567 1033500423

m n k 7 127 120 113 106 99 92 8 255 247 239 231 223

r 7 14 21 28 35 8 16 24 32

gи 1 2 3 4 5 1 2 3 4

G(X) – mod 8 211 41567 11554743 3447023271 624730022327 435 267543 156720665 75626641375

215 40

5

23157564726421

Коды БЧХ с длиной 2m -1 называют примитивными кодами БЧХ. К ним, в частности, относятся классические коды Хемминга, исправляющие однократные ошибки. К кодам БЧХ относятся также коды, длина n которых является делителем 2m -1. Например код Голея (23, 12, 7) (см. подраздел 1.4) также принадлежит классу кодов БЧХ, по-

21 скольку при m = 11 примитивный код БЧХ имеет длину n = 211 - 1 = 2047, причём это значение без остатка делится на длину кода Голея n = 23 (2047 : 23 = 89), который относится к непримитивным БЧХ- кодам [5, 6]. На основании данных табл. 3 можно построить графики зависимости скорости передачи Вк = k / n от значения скорости исправления ошибок ν= gи / n , которые приведены в [6]. Если отношение gи / n остается постоянным, то скорость передачи Вк стремится к нулю, когда n неограниченно возрастает. Как отмечалось выше, все примитивные коды БЧХ обладают конструктивным расстоянием dmin ≥ 2gи +1. Расстояние можно увеличить до 2gи + 2. Для этого нужно основной порождающий полином БЧХ - кода домножить на бином X+1, т.е. G1(X) = (Х+1) ×GБЧХ(X), что повлечёт за собой прибавление к коду одного проверочного символа, обеспечивающего проверку на чётность всех символов БЧХ - кода. Таким образом получается расширенный БЧХ - код. Адекватно можно получить укороченный (усечённый) БЧХ - код, следуя алгоритму, изложенному в подразделе 1.6. Коды Рида—Соломона (PC) являются важным и широко используемым подмножеством кодов БЧХ. Двоичный код Рида—Соломона получится, если взять основание кода q = 2s. Это означает, что каждый символ кода заменяется s -значной двоичной последовательностью. Если исходный код с основанием q исправляет ошибки кратности < gи, то полученный из него двоичный код имеет 2gи·s проверочных символов (по 2gи на каждый блок из символов) из общего числа n = s ·(2s - 1). Код может исправлять серийные ошибки (пакеты ошибок) длиной ≤ b = s ·( gи -1)+1 . Коды PC, наряду с кодами Файра (4.10), являются наиболее подходящими для исправления серийных ошибок, а также в каскадных системах кодирования в качестве внешних кодов. Построение кодеров и декодеров ЦК основывается на применении ЛПС, содержащих сдвигающие регистры. Как отмечает Р. Блейхут [5], ЛПС "были сразу использованы большинством исследователей и вошли в литературу без всяких фанфар." 1.8. Структурный состав линейных переключательных схем Цикличность перестановок при формировании разрешённых кодовых комбинаций ЦК лежит в основе техники построения кодирующих устройств (КУ) и декодирующих устройств (ДУ) циклических кодов. Эта техника применяет сдвигающие регистры (СР) в виде триггерных цепочек с теми или иными обратными связями. Такие СР называют также многотактными линейными переключательными схемами (ЛПС) и линейными кодовыми фильтрами Хафмена, который первым начал изучение ЛПС с точки зрения линейных фильтров. Кстати, Д. Хафмен является и автором принципа, состоящего в том, что "две точки зрения лучше, чем одна", получившего широкое применение в настоящее компромиссное время. При построении ЛПС используется 3 вида элементарных устройств: 1) сумматор, имеющий, как правило, два входа и один выход, причём для двоичных кодов суммирование осуществляется по модулю 2; 2) ЗУ, имеющее один вход и один выход и представляющее собой одну триггерную ячейку (один разряд) СР; 3) устройство умножения на постоянную величину, имеющее один вход и один выход. Эти устройства изображаются на схемах так, как показано на рис. 4.1.

22 Линейными переключательными схемами с конечным числом состояний называются любые схемы, содержащие конечное число сумматоров, устройств памяти и устройств умножения на константу, соединённых любым допустимым способом. В бинарном случае сумматор (равно как и вычитатель) представляет собой логический элемент "исключающее ИЛИ", а устройство памяти является устройством задержки (D-триггером). Устройства задержки, включённые последовательно, составляют СР, в ячейках которого выходной символ совпадает с входным символом в предшествующий момент времени. К СР подводится шина сдвига, с помощью которой тактовыми импульсами (ТИ) осуществляется продвижение по разрядам СР записанной кодовой информации. Как правило, шина сдвига не показывается на схемах с изображениями ЛПС. При формировании и обработке двоичных ЦК введение в схему ЛПС умножителя на константу, равную 1, эквивалентно введению дополнительного соединения, а умножитель на константу, равную 0, соответствует отсутствию такого соединения. Предполагается, что на вход СР, входящего в состав ЛПС, кодовая комбинация подаётся последовательно, с периодичностью, равной периоду следования ТИ в шине сдвига. Аналогично, последовательно во времени, появляются кодовые символы на выходе СР. Когда входом или выходом является многочлен, представляющий при двоичной обработке набор " 1" и "0", то на входном или выходном конце СР появляются только коэффициенты (" 1" или "0"), начиная с коэффициентов высших порядков. Это обуславливается тем, что при делении у делителя сначала должны быть обработаны коэффициенты высших порядков. В последующих разделах описываются схемы, используемые для умножения и деления любых многочленов на некоторый фиксированный, в частности, порождающий полином. 1.9. Умножение полиномов на базе ЛПС Схема, изображенная на рис. 4.2, используется для умножения любого полинома на входе A(X) = a0 + a1 X + a2 X2 + … + ak Xk на фиксированный полином, в частности, порождающий: G(X) = g0 + g1 X + g2 X2 + … + gr Xr . Предполагается, что первоначально все разряды СР содержат нули, а на вход коэффициенты полинома А(Х) поступают, начиная с коэффициентов высших порядков (со старших разрядов), после чего следует r нулей. Первый вариант ЛПС для умножения полиномов (рис. 4.2).

23 Произведение полиномов A(X)·G(X) = a0 g0 +(ao g1 + a1 g0)X + ... + akgrXk+r.

(4.32)

Когда на входе ЛПС появляется первый (старший) коэффициент полинома А(Х), то он умножится в первом устройстве умножения на gr и появится на выходе уже как результат перемножения akgr, проследовав "транзитом" через все схемы суммирования по модулю 2. Кроме того, ak запишется в первом разряде СР, а все остальные разряды СР будут содержать нули. Спустя единицу времени, с появлением в шине сдвига 2-го ТИ, на входе появится ak-1, который перемножится с gr и сложится в первой схеме суммирования по модулю 2 с akgr-1, сформировав на выходе сумму ak-1gr + akgr-1, т. е. второй коэффициент произведения A(X)·G(X). Дальнейшие операции производятся аналогичным образом. После r+k сдвигов СР полностью обнуляется и на выходе появляется значение a0g0, равное первому коэффициенту произведения (4.32), так что произведение на выходе ЛПС последовательно получается в полном составе. Второй вариант ЛПС для умножения полиномов показан на рис. 4.3.

Коэффициенты произведения формируются непосредственно в СР. После того, как первый символ подаётся на вход, на выходе появляется последний коэффициент (4.32) ak gr, а разряды СР содержат только нули. После одного сдвига ячейки СР содержат элементы akg0, ak g1,..., ak gr-1, a вход равен ak-1. При этом выход СР равен ak gr-1 + ak-1 gr, т. е. равен второму коэффициенту (4.32). После появления очередного ТИ в шине сдвига (не показана на рис. 4.2 и 4.3) на выходе появляется третий коэффициент (4.32). Дальнейшие операции производятся аналогичным образом. Схемы умножения могут иметь более чем один вход, если добавить к ЛПС, изображенной на рис. 4.3, вторую шину с цепочкой устройств умножения, связанных с соответствующими схемами суммирования по модулю 2. Тогда схема будет реализовывать процедуру суммирования произведений двух пар полиномов C(X) = A1(X)·G1(X) + A2(X)·G2(X) ,

(4.33)

причём ЗУ в виде СР будет только одно. Пример_5. Составить 2 схемы кодирующих устройств ЦК Хемминга (7, 4) на базе двух рассмотренных вариантов ЛПС для умножения полиномов (рис. 4.4). В качестве порождающего полинома использовать полином G (7,4) = Х3 + X +1 (см. примеры 1 и 3).

24 Напомним (см. подраздел 1.4), что применение в кодерах метода умножения приводит, к сожалению, к формированию неразделимых ЦК. 1.10. Деление полиномов на базе ЛПС Схема для деления полинома A(X) = a0 + a1 X + a2 X2 + … + ak Xk на полином G(X) = g0 + g1 X + g2 X2 + … + gr Xr представлена на рис. 4.5. Динамическое ЗУ в виде СР вначале должно содержать все нули. Для деления полиномов СР охвачен обратной связью, т. е. выход СР соединяется со входом. Для подчёркивания противоположного направления шины обратной связи коэффициент умножителя обозначается как gr-1. Однако для двоичных кодов результат умножения и деления на единицу одинаков, поэтому указанное обозначение в дальнейшем использоваться не будет. Первый вариант Л ПС для деления полиномов (рис.4. 5).

Для первых r - сдвигов, т, е. до тех пор, пока первый входной символ не достигнет конца PC, выход принимает значения, равные "0". После этого на выходе появляется первый ненулевой выход, который равен ak·gr-1 - первому коэффициенту частного. Для каждого коэффициента частного gj необходимо вычесть из делимого полином G(X). Это вычитание производится с помощью обратной связи. После k сдвигов на выходе появится частное от деления, а остаток от деления будет находиться в PC. Работу схемы легче всего понять с помощью примеров построения КУ и ДКУ на базе ЛПС, рассматриваемых далее в разделе 1.11. Второй вариант ЛПС с делением на генераторный полином (рис. 4.6).

При построении КУ ЦК, а также генераторов различных кодовых последовательностей, в частности, последовательностей максимальной длины (Мпоследовательностей), применяется в ряде случаев так называемый генераторный полином Н(Х). Этот полином называют также проверочным, если он получается при делении бинома 1+Хn на порождающий полином G(X): H(X) =

1+ X n . G (X)

(4.34)

25 При использовании этой схемы в качестве КУ ЦК исходную кодовую комбинацию А(Х) параллельно, одновременно записывают в k разрядов СР. С первым тактом на выход будет выдан коэффициент bn-1 = ak-1, произойдет сдвиг вправо в СР, и в освободившуюся ячейку памяти будет записано вычисленное значение проверочного бита rn -k-1 = h0 ak-1 + h1 ak-2+ ... + h k-1 a0. Со вторым тактом на выход будет считан коэффициент bn-2 = ak-2, произойдет сдвиг, и в освободившуюся первую ячейку СР запишется второй проверочный бит rn-k-2 = h0 ak-2 + h1 ak-3+ ... + hk-1 rn-k-1. Чеpез n-k тактов будут вычислены все n-k проверочных символов r0, r1 , …, rn-k-1 и записаны в СР. После k тактов, т. е. после вывода на выход всех информационных символов, станут выводиться проверочные символы в том же порядке, в каком они вычислялись. На выходе получается блочный код. После k тактов процесс кодирования одной комбинации Аi(Х) заканчивается, и СР принимает исходное состояние. Для кодирования следующей комбинации необходимо стереть Аi(Х), ввести в СР новую Аj(Х) и повторить цикл из n тактов. Рассмотрим более конкретно работу этой схемы на примере использования её в качестве КУ с привязкой начальных условий к данным предыдущих примеров 1, 2 и 3. Пример 6. Построить схему КУ, обеспечивающего кодирование ЦК Хемминга (7,4) с порождающим полиномом G(X) =1 + X + Х2 путём вычисления блока проверочных символов "в целом", используя проверочный полином Н(Х). Проследить по тактам процесс кодирования и состояние элементов схемы при кодировании исходной комбинации 1001 ~ 1 + X3 = A(X). Построение схемы КУ определяется проверочным полиномом (4.34) H(X) =

1+ X 7 1+ X + X

3

=1 + X + X 2 + X 4 .

Так как k = 4, то число разрядов СР равно четырём. По виду проверочного полинома определяем, что h0 = h1 = h2 = h4 = 1, h3 = 0. Схема КУ для условий примера приведена на рис. 4.7. Состояние ячеек СР и выхода схемы по тактам - в табл. 4. В исходном положении в триггерные ячейки СР записываются информационные символы Ai(X) = 1 + X3 ~ 1001. Учитывая наличие обратной связи в СР с выхода на вход, суммирование по модулю 2 выходов ячеек Х1 , Х2 и X3 даст символ записи в ячейку Х0. После первого сдвига в Х0 будет записан символ проверочной группы r1, который при последующих сдвигах продефилирует на выход СР. Из табл. 4 видно, что после n=7 тактов на выходе образуется комбинация 0111001 (старшим разрядом вперед), такая же, как в примерах 1 и 2. Таблица 4. Номер такта

Состояние ячеек 0

A(X) 1 2 3 4 5 6 7

X 1 1 1 0 1 0 0 1

1

X 0 1 1 1 0 1 0 0

2

X 0 0 1 1 1 0 1 0

Выход 3

X 1 0 0 1 1 1 0 1

-1 0 0 1 1 1 0

26 При этом триггерные ячейки СР принимают исходное значение 1001, и при необходимости возможно повторение процедуры кодирования этой же кодовой комбинации Ai(X) путём подачи очередных следующих n =7 тактов. Таким образом, этот способ кодирования так же, как и первый вариант схемы для деления полиномов, обеспечивает получение кодовых комбинаций разделимого, блочного ЦК. Кроме того, подобная ЛПС может быть использована для генерации определённой кодовой комбинации, в частности, М - последовательности. Рассмотрение вариантов построения ЛПС, выполняющих операции умножения и деления полиномов, с целью использования в кодеках ЦК, позволяет сделать следующие выводы. 1) В КУ ЦК процедура умножения полиномов приводит к получению неразделимых кодов, что усложняет их последующее декодирование. Поэтому операция умножения редко используется в устройствах формирования и обработки ЦК. 2) При делении на порождающий полином G(X) код на выходе КУ получается разделимым и СР содержит r разрядов. Так как в большинстве случаев используются ЦК, у которых число проверочных символов r существенно меньше числа информационных (r
27 вания и состояние элементов схемы при кодировании исходного полинома Ai(X) = 1+X3 ~ 1001. Схема кодера для условий примера приведена на рис. 4.8, состояние ячеек СР и выхода схемы по тактам — в табл. 5.

Наряду с вышеотмеченными особенностями построения схемы, КУ дополнено двумя ключевыми схемами, роль которых выполняют схемы логического умножения И1 и И2, соответственно. В течение первых k = 4 тактов на второй вход схемы И1 поступают ТИ, обеспечивая прохождение символов от выходного сумматора в шину обратной связи СР. Начиная с 5-го по 7-й такт, ТИ на второй вход схемы И1 не поступают, и обратная связь разрывается. В это время поступают ТИ на второй вход схемы И2, благодаря чему выход СР подключается к выходу всего КУ, обеспечивая выдачу остатка от деления кодовой комбинации Ai(X) на порождающий полином G(X) на выход, для подстыковки проверочных символов к Ai(X). Таблица 5 Состояние

НомерВход такта

ячеек

X0 X1 X2 0 1 2 3 4 5 6 7

-1 0 0 1 ----

0 1 0 1 0 0 0 0

0 1 1 1 1 0 0 0

0 0 1 1 1 1 0 0

Из табл.5 видно, что после 4-го такта в СР образуется остаток 011, т.е. ключей R(X)=X+X2, а в течение n тактов на выход поступает кодовая комбинация 0111001 ~ 2 3 6 Выход КЛ1 КЛ2 X + Х + Х + X (старшим разрядом вперед) — см. пример 1. Декодер для кода Хемминга (7, 4). -При аппаратурной реализации декодеров 1 Замкнут РазомЦК для определения синдрома использу0 кнут ют схему, осуществляющую процедуру 0 деления полинома на полином (см. рис. 1 1 4.5). При построении ДУ следует допол1 Разом- Замкнут нительно включать ЗУ на k элементов и 0 кнут схему опроса остатка при делении.

Эта схема состоит из схемы логического сложения (ИЛИ) на r входов и схемы логического умножения (И) на два входа. СР и обратные связи должны соответствовать структуре порождающего полинома G(X), т. е. число ячеек СР должно быть равным r, а замкнутая обратная связь должна соответствовать ненулевым коэффициентам полинома G(X).

28 Пример 8. Построить схему ДУ для ЦК Хемминга (7, 4) с порождающим полиномом G(X) = 1 + X + X3 и по тактам сдвигающих импульсов проследить за его работой. Схема ДУ должна решать задачу обнаружения ошибок. Таблица 6 Вход Номер B(X) такта Исх. -сост.

1 0 0 1 1 1 0

1 2 3 4 5 6 7

Состояние ячеек

X0

X1

X2

Выход СР

0

0

0

--

1 0 0 0 1 0 0

0 1 0 1 0 0 0

0 0 1 0 1 0 0

0 0 0 1 0 1 0

На рис.9 приведена схема ДУ, в табл.6 представлены состояния ячеек СР при декодировании входной кодовой комбинации Bi(X)=X + X2 + Х3 + Х6 ~ 0111001, принимаемой без ошибок. Декодирующее устройство работает следующим образом. Кодовая комбинация Bi(X) старшим разрядом вперёд поступает на СР для определения остатка при делении и в ЗУ на k элементов через открытую схему И1, которая через k тактов закрывается, так как прекращается подача из синхронизатора ТИ на один из входов схемы И1.

При этом в ЗУ запоминаются k информационных символов принимаемой кодовой комбинации Bi(X). В СР поступают все n элементов Bi(X), и после n тактов происходит опрос состояния ячеек СР путём подачи циклового импульса с синхронизатора на схему И2. Если R(X) ≠ 0, то на выходе схемы И2 импульс не появится и считывания с ЗУ принятых информационных символов не произойдет. Если R(X) = 0, то появившийся на выходе И2 импульс считывает Ai(X) на выход и выдаёт четыре информационные бита получателю сообщений.

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

29 длинных кодов. Для длинных ЦК разработаны специальные итеративные процедуры декодирования с исправлением нескольких ошибок, например, метод Берлекэмпа или более совершенный итеративный алгоритм Тренча-Берлекэмпа-Месси (ТБМ-метод), оперирующий с полиномами над полями Галуа. Различные методы декодирования так же, как и коды, получают авторские наименования. Известны алгоритмы декодирования Хемминга, Питерсона, Ченя, Мэггита, Витерби и других [5—10]. В лабораторной работе "Циклические коды" используется синдромный метод декодирования ввиду малой длины исследуемого БЧХ-кода. Декодирующие устройства для кодов, предназначенных только для обнаружения ошибок, по существу, не отличаются от схем КУ (см. подраздел 1.11). В них добавляется лишь буферный регистр для хранения принятого сообщения на время проведения операции деления. Если остаток-синдром при делении оказывается нулевым, что свидетельствует об отсутствии ошибки, то информация с буферного регистра считывается в дешифратор сообщения ПС. Если остаток обнаружен, что свидетельствует о наличии ошибки, то информация в буферном регистре уничтожается и на передающую сторону к ИС посылается импульс запроса повторной передачи по обратному каналу связи. В случае исправления ошибок схема ДУ, естественно, усложняется. Информацию о разрядах, в которых произошла ошибка, т. е. о виде шумового вектора Z(X) (4.16), содержит, как и ранее, синдром, получаемый в результате деления полиномов. Структурная схема ДУ, решающего задачу исправления ошибок, представлена на рис. 4.10.

Символы подлежащей декодированию кодовой комбинации, возможно, содержащей ошибку, последовательно, начиная со старшего разряда, вводятся в n-разрядный буферный регистр сдвига и одновременно в схему определителя синдрома, где за n тактов деления определяется остаток, который в случае синхронной, непрерывной передачи кодовых комбинаций сразу же переписывается в аналогичный СР схемы анализатора синдрома. В состав схемы анализатора синдрома может входить ПЗУ, в котором записаны все возможные конфигурации синдромов с соответствующими им шумовыми векторами. Кодовые комбинации шумовых векторов (4.16) содержат "единичные" символы на тех позициях, которые в процессе передачи сообщения по каналу связи оказались искажёнными помехами. Локатор ошибок (определитель места ошибок) представляет собой комбинаторно-логическую схему, выдающую на выход единичные символы в те моменты времени, когда каждый из ошибочных символов принятой кодовой комбинации занимает в буферном регистре крайнюю правую ячейку. При последующем

30 тактовом сдвиге локатор ошибки (детектор ошибки) формирует символ "1", который поступает на сумматор коррекции, представляющий собой схему суммирования по модулю 2, где исправляется искажённый символ. Одновременно по цепи обратной связи с выхода локатора ошибки подаётся единичный символ на анализатор синдрома, что в ряде конкретных схемных решений построения анализатора упрощает его построение на базе ЛПС без использования ПЗУ [5]. Сложность анализатора синдрома и локатора ошибки зависит от гарантированного числа исправляемых и обнаруживаемых ошибок. Естественно, простейшие схемные решения получаются при обработке кодов, рассчитанных на исправление единичных ошибок. Как видно из рассмотрения логики работы структурной схемы декодера (см. рис. 4.10), наиболее сложной частью его является необходимость запоминания заранее вычисленных синдромных полиномов и соответствующих им векторов ошибок. Достоинством ЦК как раз и является то, что анализатор синдрома можно значительно упростить, воспользовавшись алгебраической структурой кода для отыскания связей между синдромами при числе исправляемых ошибок gи>1. Опираясь на эти связи, можно запомнить в ПЗУ только полиномы ошибок, соответствующие некоторым типичным синдромным полиномам, а вычисление остальных осуществить затем с помощью простых вычислительных алгоритмов. Именно на таких принципах работают различные варианты декодеров Мэггита [5,9]. 2.

ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ

Перед началом выполнения лабораторной работы " Циклические коды" студент должен получить у преподавателя номер порождающего полинома G(X) ЦК, задаваемого в восьмеричной системе счисления (табл. 7), и информационное слово в виде десятичного числа от 1 до 127. Таблица 7 №

G(X)

№

G(X)

№

G(X)

№

G(X)

1

23

7

117

13

427

19

2041

2

31

8

135

14

673

20

2467

3

37

9

171

15

721

21

3545

4

41

10

213

16

1163

22

4657

5

53

11

321

17

1315

23

6143

6

65

12

347

18

1471

24

7531

Работа "Циклические коды" выполняется на персональных ЭВМ, в среде операционной системы MS-DOS. Для выполнения лабораторной работы (ЛР №4) необходимо выбрать соответствующую позицию меню и нажать клавишу <ENTER>. После небольшой паузы на экране дисплея появится заголовок "Часть1" и приглашение ввести порождающий полином. В случае ввода ошибочных символов выдаётся сообщение "Ошибка ввода, повторите", после чего необходимо заново ввести строку, в которой была допущена ошибка. Для прекращения выполнения лабораторной работы достаточно в любой момент нажать клавишу < ESС>. Программа выполнения работы включает четыре части.

31 1. Заданный порождающий полином необходимо преобразовать в двоичную и в полиномиальную формы, а затем ввести с клавиатуры. Ввод полинома по степеням заключается в следующем: вводятся через запятую только степени полинома, а затем нажимается клавиша <ENTER>. Например, полином Х10 + Х4 + Х3 + Х+1 вводится как 10, 4, 3, 1, 0 <ENTER>. Программа допускает при двоичном вводе отбрасывание ведущих нулей. Так, слово 00101101 можно вводить как 101101. Если введённые формы полинома не соответствуют исходной восьмеричной, то выводится сообщение об ошибке и повторяется ввод информации до rex пор, пока она не будет введена правильно. Таким образом, довести до конца работу можно только правильно выполнив каждый её пункт. Зная длину кодового слова (n = 15) и порождающий полином, надо рассчитать и ввести значения избыточности и скорости порождаемого этим полиномом циклического кода. 2. Этот раздел лабораторной работы посвящен процедурам умножения и деления полиномов на исходный порождающий полином G(X) при помощи ЛПС (см. подразделы 1.9 и 1.10). На экране последовательно изображаются три "заготовки" ЛПС: две ЛПС умножения и одна деления, с пронумерованными местами для перемычек. Задача состоит в правильном размещении перемычек согласно порождающему полиному G(X). Перемычки расставляются путём ввода через запятую их номеров. 3. В третьей части работы осуществляется синтез порождающей матрицы циклического БЧХ-кода (15, 7) по его порождающему полиному с G(X) =Х8+X7+Х6+ Х4+1 (см. подразделы 1.5 и 1.6). 3.1. На экран выводятся основные данные БЧХ-кода (15,7): порождающий полином и минимальное кодовое расстояние d = 5. Эти данные следует выписать, так как они понадобятся в дальнейшем при работе. 3.2. Рассчитать и построчно ввести в двоичной форме порождающую каноническую матрицу данного БЧХ-кода. Под канонической подразумевается матрица, состоящая из двух подматриц - единичной и кодирующей. Такое построение порождающей матрицы даёт разделимый БЧХ-код. 3.3. По порождающему полиному и минимальному кодовому расстоянию требуется рассчитать и ввести проверочный полином данного БЧХ-кода, а также количество гарантированно исправляемых и обнаруживаемых им ошибок. 3.4. Из канонической порождающей матрицы БЧХ-кода (15,7) получить порождающую матрицу укороченного БЧХ-кода (13, 5) и построчно ввести её. 4. Кодирование и декодирование циклическим БЧХ-кодом (15,7). 4.1. Полученное в начале работы информационное слово (десятичное число в пределах от 1 до 127) ввести с клавиатуры. 4.2. Преобразовать информационное слово из десятичной формы в двоичную, а затем в полиномиальную и последовательно ввести. 4.3. По информационному слову рассчитать кодовое слово разделимого БЧХ-кода (15,7) и ввести его двоичный эквивалент. Кодовое слово можно вычислить, умножив вектор информационного слова на порождающую матрицу или выделив остаток от деления на порождающий полином информационного полинома, предварительно умноженного на Х8, в случае применения кода (15,7). 4.4. ЭВМ троекратно рассчитывает случайный вектор ошибок, содержащий одну, две и три ошибки, и выводит на экран исходное кодовое и искажённое слово, отметив в нём ошибочные символы. Необходимо вычислить и ввести двоичную форму синдрома, соответствующего искажённому кодовому слову. ЭВМ проверяет правильность ввода и формирует, исходя из полученного синдрома, шумовой вектор, который поразрядно суммируется по модулю 2 с искажённым кодовым словом. Таким образом вы-

32 числяется выводимое на экран исправленное кодовое слово. Затем ЭВМ рассчитывает и отображает синдром исправленного кодового слова. Некоторые комбинации трёхкратных ошибок данный БЧХ-код не в состоянии исправить, так как его минимальное кодовое расстояние равно 5. Синдромы кодовых слов можно рассчитывать двумя способами: умножая двоичное кодовое слово на транспонированную проверочную матрицу или деля полином кодового слова на порождающий полином, определяя остаток (см. подраздел 1.4). В конце лабораторной работы выводится информация о количестве допущенных ошибок, а затем приглашение к вводу номера группы и фамилии студента, выполнившего работу. Эта информация автоматически дополняется датой и временем выполнения работы, введённым полиномом и информационным словом, распределением ошибок исполнителя по разделам работы. Все эти данные требуются для последующего просмотра преподавателем. Студентам, выполнившим работу, необходимо сообщить об этом преподавателю для отметки в лабораторном журнале, предъявив данные о числе допущенных ошибок по разделам работы, подписанные оператором ЭВМ. 3.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Пояснить принципы помехоустойчивого кодирования. 2. Циклические коды и их особенности. 3. Порождающий и проверочный полиномы ЦК и их основные особенности. 4. Укороченные ЦК. Порождающие и проверочные матрицы укороченных кодов и их порождающие полиномы. 5. Принципы кодирования и декодирования ЦК при помощи ЛПС. 6. Построение канонической и порождающей матрицы по порождающему или проверочному полиномам. Покажите на примере. 7. Определите верхнюю границу минимального кодового расстояния заданного (n, k) ЦК. 8. Закодируйте БЧХ - кодом (15,7) произвольное кодовое слово при помощи порождающей матрицы и полинома. 9. Охарактеризуйте различие между разделимыми и неразделимыми кодами. Приведите примеры. 10. Объясните суть синдромного метода декодирования и его отличие от декодирования по методу максимального правдоподобия. 11. Почему синдром исправленного кодового слова всегда равен нулю, даже если кратность ошибки превосходит корректирующую способность кода и поэтому исправленное кодовое слово неверно? 12. Как связаны между собой минимальное кодовое расстояние и кратности исправляемых и обнаруживаемых им ошибок? 13. В чём заключается трудность декодирования с исправлением ошибок? 14. При обнаружении ошибки в кодовой комбинации на стороне приёма каковы пути её исправления? 15. В чём состоят особенности кодов Абрамсона и Файра, в каких случаях их целесообразно применять? 16. Какое главное отличие кодов Рида-Соломона от БЧХ-кодов, в каких случаях находят применение коды Рида-Соломона? 17. Охарактеризуйте достоинства и особенности кода Голея. 18. Дайте определение оператора сдвига, с какой целью он применяется при циклическом кодировании?

33 Литература 1. Никитин Г. И. Первичные коды: Метод. указ./ ЛИАП. Л., 1984. 28 с. 2. Никитин Г. И. Эффективные коды: Метод, указ./ ЛИАП. Л., 1987. 28 с. 3. Никитин Г. И., Антипова И. Б., Красновидов А. В. Корректирующие коды: Метод. указ./ ЛИАП. Л., 1989. 32 с. 4. Журавлев А. К., Никитин Г. И. Радиотехнические системы передачи информации: Учеб. пособие/ ЛИАП. Л., 1984. 86 с. 5. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986. 576 с. 6. Питерсон У., Уэлдон Э, Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976. 600 с. 7. Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодировании). М.: Наука, 1983. 144 с. 8. Харкевич А. А. Борьба с помехами. М.: Физматиздат, 1963. 276 с. 9. Колесников В. Д., Мирончиков Е. Т. Декодирование циклических кодов. М.: Связь, 1968. 10. Замрий А. С. Помехоустойчивые коды: Учеб. пособие/ ЛВВИУС. Л., 1990. 58 с. 11. Варакин Л. Е, Системы связи с шумоподобными сигналами. М.: Радио и связь, 1985. 384 с. 12. Никитин Г.И., Поддубный С.С. Помехоустойчивые циклические коды: Учеб.пособие/ СПбГУАП. СПб., 1998. 72 с. СОДЕРЖАНИЕ Список основных сокращений .................................... ……………………………. 3 Введение ................................................................... ……………………………. 4 1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ К ЛАБОРАТОРНОЙ РАБОТЕ ….. ……………………………………………… 4 1.1. Классификация корректирующих кодов ............... …………………………… 4 1.2. Полиномиальное определение циклических кодов и операции с ними ........ ......................................... ……………………………. 5 1.3 Порождающие полиномы циклических кодов..... ……………………………. 7 1.4. Принципы формирования и обработки разрешённых кодовых комбинаций циклических кодов ............................ ……………………………. 10 1.5. Построение порождающих и проверочных матриц циклических кодов …. 15 1.6. Укороченные циклические коды.......................... ……………………………. 18 1.7. Циклические коды Боуза—Чоудхури—Хоквингема ………………………. 20 1.8. Структурный состав линейных переключательных схем …………………. 21 1.9. Умножение полиномов на базе ЛПС................... ……………………………. 22 1.10. Деление полиномов на базе Л ПС ………………………………………….. 24 1.11. Кодирующее и декодирующее устройства для кода Хемминга (7,4)…… 26 1.12. Принципы построения декодирующих устройств для циклических кодов с исправлением ошибок ……………………………… 28 2. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ "ЦИКЛИЧЕСКИЕ КОДЫ" …………………………………………………………… 30 3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ ………………………………………. 32 Литература ……………………………………………………………………… 33

Графика и компьютерная вёрстка Романова М.Я. 2003 г.