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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ	4
1 Основные сведения о циклических кодах	5
2 Расчет параметров циклического кода	17
3 Разработка структурной схемы канального кодека циклического кода	19
3.1 Разработка структурной схемы кодера циклического кода	19
3.2 Разработка структурной схемы декодера циклического кода	20
4 Разработка функциональной схемы кодека циклического кода	23
4.1 Разработка функциональной схемы  кодера	23
4.2 Разработка функциональной схемы  декодера	24
5 Разработка принципиальной схемы кодека	26
5.1 Выбор и обоснование элементной  базы проектируемого кодека	26
5.2 Разработка принципиальной схемы  кодера	27
5.3 Разработка принципиальной схемы декодера	33
Заключение	38
Литература	39
Приложение А Принципиальная электрическая схема кодека	40
Приложение В Принципиальная электрическая схема декодера	41

 

 

Введение

 

Циклические коды являются подклассом в классе линейных блоковых кодов, удовлетворяющих определенным требованиям. Свое название данные коды получили по причине того, что основной операцией построения кодовых последовательностей (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. Для сложения старших разрядов полиномов делимого и делителя сумматора не надо - результат сложения заранее известен, а именно равен нулю.