Разработка кодека циклического кода

СОДЕРЖАНИЕ

Введение

Циклические коды являются подклассом в классе линейных блоковых кодов, удовлетворяющих определенным требованиям. Свое название данные коды получили по причине того, что основной операцией построения кодовых последовательностей (Fi(x)) является цикл, а точнее циклическая перестановка двоичных символов разрешенных кодовых последовательностей. Циклическим кодом называется линейный блоковый код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых последовательностей, образующих данный код. С математической точки зрения ЦК является идеалом в линейной коммутативной алгебре многочлена (полинома) n-го порядка по модулю двучлена xn-1 над полем коэффициентов. Это означает, что кодовые последовательности ЦК имеют длину “n” двоичных кодовых символов и описываются полиномами степени (n-1), в которых коэффициентами при соответствующих степенях формальной переменной, обозначаемой через “x”, являются двоичные символы кодовой последовательности. Формальная переменная “x”, которая носит название оператора Хаффмана или оператора задержки и не оказывает никакого влияния на свойства кода.

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

1 ОСНОВНЫЕ СВЕДЕНИЯ  О ЦИКЛИЧЕСКИХ КОДАХ

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

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

,                                         (1)

где - контрольные символы;

       - информационные символы.

При описании циклических кодов наиболее удобной является запись двоичной комбинации циклического кода b в виде многочлена b(х) некоторой фиктивной переменной х. Двоичная комбинация m-разрядного первичного кода записывается аналогично в виде информационного многочлена m(x).

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

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

Построение циклического кода основано на использовании так называемого образующего или порождающего полинома р(х). Он должен быть неприводимым многочленом, т.е. делиться только сам на себя и на единицу. Образующий полином выбирается в разложении двучлена на неприводимые многочлены [3, 4]. Старшая степень р(х) определяется числом контрольных символов k. Полином называется проверочным. Его высшая степень совпадает с числом информационных разрядов m первичного кода.

Кодовые комбинации циклического кода помимо общих для групповых кодов свойств удовлетворяют двум условиям:

1. без остатка делятся на образующий полином, т.е.

               (2)

2) при  умножении на проверочный полином  дают тождественный нуль по  модулю двучлена  , т.е.

.    (3)

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

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

Циклический сдвиг кодовой комбинации b на i шагов влево (вправо) равносилен умножению полинома b(х) на одночлен по модулю двучлена .

Способы описания циклического кода:

Наиболее целесообразно циклический код представлять в виде разделимого (n,m) кода. Тогда алгоритм кодирования определяется выражением

                                           (4)

где  .

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

.                                                     (5)

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

Кроме образующей матрицы, циклический код можно описать с помощью проверочной матрицы. В принципе ее можно представить в канонической форме , как для группового кода. Однако эта форма не позволяет использовать свойство цикличности для коррекции ошибок. В этом случае обнаружение и исправление ошибок подобно групповому коду. Наибольшее применение на практике имеет циклическая форма проверочной матрицы H*k,n. Ее первая строка зависит от вида проверочного полинома h(x), а остальные строки получаются циклическим сдвигом вправо первой строки. Первая строка проверочной матрицы связана с видом проверочного полинома следующим правилом. Полином h(x) представляется в виде кодовой комбинации. Запись этой комбинации в обратном порядке и приписывание к ней справа (k-1) нулевых символов дает первую строку матрицы .

Строки проверочной матрицы отражают состав проверок на четность

, ,                               (6)

где - элемент j-й строки и i-го столбца проверочной матрицы.

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

.                                                 (7)

Построение циклического кода:

Прежде чем строить циклический код, нужно знать его параметры m, d, k и n=m+k. Тогда построение кода по сути дела сводится к выбору образующего полинома p(x). Образующий полином следует искать по таблице разложения двучлена на неприводимые сомножители (см. [3, 4]).

Полином р(х) должен удовлетворять двум условиям:

1) степень  полинома равна k;

2) число  ненулевых членов  .

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

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

1) число  различных остатков  ;

2) число  единиц каждого остатка (его вес) ;

3) остатки  должны отличаться друг от  друга в числе разрядов  .

При выполнении этих требований полином р(х) обеспечивает построение (n,m) циклического кода с кодовым расстоянием d.

Если в расположении двучлена не удается найти многочлен степени k и длины , то прибегают к построению укороченного циклического кода.

Кодеры циклического кода:

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

Реализация умножения и деления полиномов

А) Реализация умножения.

Представим образующий полином в виде

  ,                                                    (8)

где k - число контрольных разрядов;

pi - символы двоичного алфавита, т.е. .

Информационный полином в виде

,                                               (9)

где m - число информационных разрядов;

символы .

Тогда произведение можно записать следующим образом:

.                       (10)

Пусть информационный полином подается на устройство умножения старшим разрядом вперед. Умножение выполняется потактно. Рассмотрим последовательно такты произведения.

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

2-й такт. При нужно сложить по mod 2 текущее значение информационного кода с предыдущим значением и результат выдать на выход. Для этого предыдущее значение нужно запоминать. Отсюда следует реализация второго такта на базе Dt-триггера с внутренней задержкой и сумматора по mod 2 (см. рисунок 1).

Микросхема серии 155

  Dt-триггер

Рисунок 1 - Реализация второго такта

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

3-й такт. Результат сложения первых двух  слагаемых дает схема 2-го такта. Для добавления 3-го слагаемого  нужен еще Dt-триггер регистра  сдвига РС и сумматор по mod 2 (см. рисунок 2).

Рисунок 2 – Реализация добавления третьего слагаемого

Таким образом, структура устройства умножения двух полиномов принимает вид, показанный на рисунке 3. Исходное состояние - все триггеры в нулевом состоянии. Число триггеров равно k. Наличие связи рi на сумматор по mod 2 имеет место при коэффициенте .

Рисунок 3 – Устройство умножения двух полиномов

Модификация устройства умножения приведена на рисунке 4.

Рисунок 4 – Модификация устройства умножения двух полиномов.

В исходном состоянии все триггеры находятся в нулевом состоянии. Связь рi имеет место при и отсутствует при . Число сумматоров по mod 2 равно числу отличных от нуля коэффициентов рi минус 1.

Б) Реализация деления. Деление есть сдвиг делителя до совпадения со старшим разрядом делимого и их сложение по mod 2. Операция продолжается до тех пор, пока старшая степень остатка станет меньше степени делителя. Пример на рисунке 5 - это 3-х регистровая реализация деления (соответствует делению столбиком). Ее можно сделать последовательно (потактно) на одном регистре.

Рисунок 5 – Трехрегистровая реализация деления

Структура устройства деления полиномов представляет собой регистр сдвига с сумматорами по mod 2. Обратные связи регистра соответствуют виду полинома р(х). Число триггеров равно k. Число сумматоров равно числу ненулевых членов полинома р(х) минус 1. Для сложения старших разрядов полиномов делимого и делителя сумматора не надо - результат сложения заранее известен, а именно равен нулю.

Структуры кодирующих устройств:

I тип. Алгоритм кодирования описывается выражением

                                            (11)

Структурная реализация кодера показана на рисунке 6.

Рисунок 6 – Структурная реализация кодера I типа

Схема деления отличается от ранее рассмотренной схемы. Здесь коэффициенты m(x) участвуют в обратной связи не через k тактов, а сразу с первого такта.

Принцип работы. Исходное положение: электронный ключ ЭК - в положении 1, триггеры - в нулевом состоянии. В регистре через m тактов образуется остаток r(x). На (m+1)-м такте ЭК переключается в положение 2 и остаток из регистра сдвига выдвигается в линию связи.

2. II тип. Алгоритм кодирования описывается выражением

                                         (12)

Структурная реализация кодирующего устройства приведена на рисунке 7.

Рисунок 7 – Структурная реализация кодера II типа

3) III тип. Алгоритм кодирования описывается выражением- , .

                              (13)

где - элементы проверочной матрицы в циклической форме. Для каждого j при i = 0,1,...,m-1 они определяются проверочным полиномом в форме

, где символы  .

Структурная реализация кодера с использованием многовходового сумматора по mod2 приведена на рисунке 8.

Рисунок 8 – Структурная реализация кодера III типа

Принцип работы. ЭК - в положении 1. За m тактов регистр заполняется. На (m+1)-м такте ЭК переводится в положение 2. При этом на каждом последующем такте один информационный символ выдается в канал связи и одновременно формируется контрольный символ, который записывается в ячейку регистра. Через (m+k) тактов формирование контрольных символов заканчивается. ЭК переводится в положение 1. В течение последующих m тактов содержание регистра выдается в канал с одновременным заполнением ячеек регистра новой последовательностью информационных символов.

Мажоритарные коды:

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

                               (13)

Например, для циклического кода (21,11) с образующим многочленом получим  .

В ячейки регистра сдвига записываются информационные символы в порядке, указанном цифрами в ячейках регистра сдвига. После сигнала “пуск” при каждом такте происходят продвижение символов “1” в ячейках регистра на один символ, а о крайнюю левую ячейку (11) записывается символ, значение которого равно сумме по модулю два символов, находящихся в ячейках 1, 4, 5. 10. В ячейку 11 записываются корректирующие символы, которые являются линейной комбинацией информационных и корректирующих символов, что является характерной чертой линейного блочного кода. Таким образом, генераторный полином определяет уравнения проверок.

Рисунок 9 - Кодер циклического кода (21, 11)

Рассмотрим процедуру мажоритарного декодирования. Будем рассматривать код (21,11).

В соответствии с проверочной матрицей можно записать десять проверочных уравнений:

Выберем теперь такие проверочные уравнения или их комбинации (суммы по модулю два), в которых повторяется какой-либо один символ. Такие соотношения позволяют выразить этот символ несколькими способами в виде линейной комбинации остальных символов. Каждый способ выражения данного символа через линейную комбинацию других символов назовем контрольной проверкой. Определим систему разделенных проверок, как такое множество контрольных проверок, в котором: 1) некоторый заданный символ а, входит в каждую контрольную проверку множества и 2) любой другой символ аj , j i входит не более, чем в одну контрольную проверку. Поэтому искажение одного символа в кодовом слове может нарушить только одну проверку, а которую входят искаженный символ. Две ошибки могут исказить не более двух проверок и t ошибок исказят не более t проверок и т. д. Очевидно, для правильного декодирования данного символа ai достаточно, чтобы система разделенных проверок содержала не менее 2t + 1 контрольных проверок, если при приеме искажено t символов. Тогда значение символа можно определять с помощью решения “по большинству”. Если рассматриваемый код циклический, то для декодирования остальных символов также может быть использована выбранная система разделенных проверок, поскольку контрольным соотношениям удовлетворяет любое кодовое слово и в том числа слово, получаемое из данного циклическим сдвигом. При этом для декодирования символа ai+u достаточно провести циклических сдвиг символов кодового слова на u символов и применить решение по большинству, используя систему разделенных проверок.

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

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

2 РАСЧЕТ ПАРАМЕТРОВ ЦИКЛИЧЕСКОГО КОДА

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

(

где n=14 - число символов кодовой последовательности;

k = 6 - количество информационных символов в передаваемом блоке;

= 8 - минимальное кодовое расстояние.

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

l = n-k=14-6=8 двоич. симв.                                        (14)

Кратность исправляемых ошибок

                                        (15)

Вероятность ошибки на выходе декодера определяется по формуле

                                       (16)

где - вероятность ошибки кодера;

- число  сочетаний.

.

Коэффициент повышения достоверности  рассчитывается по формуле

                                      (17)

Относительная избыточность кода

.                       (18)

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

                                                       (19)

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

3 РАЗРАБОТКА  СТРУКТУРНОЙ СХЕМЫ КАНАЛЬНОГО  КОДЕКА ЦИКЛИЧЕСКОГО КОДА

1. Разработка структурной схемы кодера циклического кода

Для разработки структурных схем кодера  определим его основные функции и требуемые для их реализации функциональные блоки (узлы).

Основные функции кодера:

1) формирование l=n-k =14-6=8проверочных символов;

2)формирование "n" (n=14 кодовых символов путем объединения "k" (k=6) информационных и "l" (l=8) проверочных символов в единый кодовый поток.

Для реализации данных функций необходимы следующие функциональные блоки:

- ФПСк – формирователь проверочных символов кодера;

- М2- блок сумматоров по модулю два;

- КОИ-n/1 (КОИ-14/1) - коммутатор объединения информации единый поток.

Кроме того, для нормального функционирования блоков кодера необходимы ФСУ (формирователь сигналов управления) и ключи управления работой кодера.

В соответствии с вышеперечисленным, обобщенная структурная схема кодера будет иметь построение, приведенное на рисунке 10.

Рисунок 10 – Обобщенная структурная схема кодера

Кодер работает следующим образом. В первоначальный момент времени ключ КЛ.1 открыт, а ключ КЛ.2 – закрыт. Передаваемые информационные символы в течении 6-ти тактов одновременно поступают через коммутатор объединения информации КОИ 14/1 в канал связи и на вход ФПСк, где формируются проверочные символы по правилу

                                           (20)

По окончанию 6-го такта положение ключей меняется на обратное, т.е. КЛ.1 закрывается, а ключ КЛ.2 открывается и далее в течении 8-ми тактов из ФПСк в канал связи считываются сформированные проверочные символы. По окончанию 14-го такта будет сформирована 1-ая кодовая комбинация циклического кода. Ключи кодера возвращаются в исходное состояние и на вход кодера поступает следующий передаваемый информационный блок, кодирование которого осуществляется аналогичным образом.

Принцип работы кодера циклического кода поясняется временными диаграммами, приведенными на рисунке 11.

Рисунок 11 – Временные диаграммы сигналов управления ключами кодера

2. Разработка структурной схемы декодера циклического кода

Основными функциями декодера являются:

1. Запись  принятых кодовых символов  в последовательный регистр сдвига (RG);

2. Формирование системы раздельных проверочных уравнений;

3. Декодирование переданных символов или формирование информационных символов;

4. Выдача информационного символа получателю с одновременной записью данного символа в регистр сдвига.

Для реализации данных функций необходимы следующие функциональные блоки:

- последовательный  регистр сдвига на n=14 ячеек памяти RG;

- коммутатор  K;

- формирователь  системы раздельных проверочных  уравнений ФС РПУ;

- мажоритарный  элемент МЭ;

- ключи управления  КЛ;

ФСУд – формирователь сигналов управления декодера

Структурная схема декодера ЦК с параметрами ( ) = (14,6,8)  при формировании системы связанных проверок имеет построение, приведенное на рисунке 12.

Принцип работы декодера циклического кода с мажоритарным алгоритмом декодирования  поясняется временными диаграммами, приведенными на рисунке 13.

В первоначальный момент декодирования ключ КЛ1 – открыт, а ключ КЛ2 – закрыт. Входные кодовые символы (n=14) через коммутатор записываются в регистр сдвига (RG) с одновременным формированием системы раздельных проверок.

Рисунок 12 - Структурная схема декодера циклического кода 

Рисунок 13 – Временные диаграммы сигналов управления ключами декодера

По окончании n=14-го такта положение ключей меняется на обратное, т. е. КЛ1 - закрыт, а КЛ2 - открыт. К этому же моменту времени будут уже получены результаты сформированных связанных проверочных уравнений.

На n+1=14+1=15 такте мажоритарным элементом формируется и выдается первый информационный символ а1, который поступает к получателю информации и по цепи обратной связи через коммутатор (К) на вход последовательного регистра сдвига. По окончании n+2=15+2=17 такта формируется и выдается второй информационный символ а2, а n+3=14+3=18 такта – третий информационный символ а3 . По окончании n+k=14+6=20 такта ключи 1 и 2 возвращаются в исходное состояние и в RG декодера записываются кодовые символы следующей кодовой последовательности и декодирование которых осуществляется аналогичным способом.

4. РАЗРАБОТКА  ФУНКЦИОНАЛЬНОЙ СХЕМЫ КОДЕКА  ЦИКЛИЧЕСКОГО КОДА

4.1 Разработка  функциональной схемы кодера

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

Формирователь проверочных символов выполняется в виде последовательного регистра сдвига со встроенными сумматорами по модулю два и обратной связью. Число ячеек памяти регистра сдвига определяется максимальной степенью порождающего полинома, т.е. m=8. Нумерацию ячеек памяти принято считать слева направо или справа налево. Нумерацию принимаем справа налево. Число сумматоров по модулю 2 равно весу образующего полинома Р(х) минус единица p=4-1=3. Сумматоры по модулю 2 ставятся перед ячейками памяти, соответствующим ненулевым членам образующего полинома Р(х), исключая его старшую степень. Таким образом, ФПСк будет иметь вид, приведенный на рисунке 14.