Руководство к лабораторной работе №4 - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1страница 2
Похожие работы
Название работы Кол-во страниц Размер
Методические указания к лабораторной работе 7 для студентов по специальности... 1 280.05kb.
Отчет по лабораторной работе №6 По теме: Сериализация 1 34.01kb.
Перед установкой станка внимательно изучите настоящее руководство... 7 719.69kb.
Отчет по Лабораторной работе №2 1 27.39kb.
Методические указания к лабораторной работе по курсу «Теория волновых... 1 124.66kb.
Исследование видеодетектора движения и тв-камеры для охранной системы... 1 164.81kb.
Компрессор руководство по эксплуатации 1 115.48kb.
Руководство по работе с модулем «Поисковая оптимизация» (seo) 1 103.28kb.
Методические указания к лабораторной работе 1 139.06kb.
Задания к лабораторной работе №4 1 43.3kb.
Гудз Г. С., Глобчак М. В., Еременко П. И. Методические указания к... 1 68.04kb.
Скачать, поругать, или обсудить бетку 1 42.9kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Руководство к лабораторной работе №4 - страница №1/2



Министерство образования Российской Федерации

Таганрогский государственный радиотехнический университет

РУКОВОДСТВО
к лабораторной работе №4

Декодирование циклических кодов
по курсу
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНОЙ ТЕХНИКИ

Для студентов специальности 190900,190304


Таганрог 2000

УДК 621.391.256(076.5)


Составитель С.В. Кавчук
Руководство к лабораторной работе №4 "Декодирование циклических кодов" по курсу "Теоретические основы информационно-измерительной техники". Таганрог: Изд-во ТРТУ, 2000.24c.

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


Табл. 6. Ил. 9. Библиогр. : 3 назв.


Рецензент С.В. Николаев, канд. техн. наук, доцент кафедры

АСНИиЭ ТРТУ.

1. ЦЕЛЬ РАБОТЫ

Изучение принципов обнаружения и исправления ошибок при декодировании циклических кодов и способов технической реализации устройств декодирования.



2. ПРОГРАММА РАБОТЫ

2.1. Программа домашней подготовки
к лабораторной работе

2.1.1. Изучить способы описания циклических кодов и методы обнаружения и исправления ошибок при их декодировании.

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

2.1.3. Для заданного варианта синтезировать структурную схему декодирующего устройства на основе свойства образующего полинома.

2.1.4. Синтезировать структурную схему декодирующего устройства на основе свойства проверочного полинома.

2.2. Программа выполнения лабораторной работы

2.2.1. Ознакомиться с диалоговой программной системой моделирования цифровых устройств на ПЭВМ и составом дискретных элементов в ее библиотеке.

2.2.2. Составить из библиотечных элементов системы моделирования функциональные схемы декодирующих устройств согласно варианту индивидуального задания.

2.2.3. Создать в диалоге на ПЭВМ программные модели исследуемых устройств и проверить путем моделирования их работоспособность.

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

3. ОСНОВНЫЕ СВЕДЕНИЯ

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

3.1.1. Групповой циклический код принято обозначать (n,m), где n - длина кодовой комбинации, m - число информационных символов или разрядов первичного неизбыточного кода. При этом число контрольных символов k = n - m.

Двоичная комбинация разделимого циклического кода имеет вид

,

где  контрольные символы и  информационные символы.

При описании циклического кода наиболее удобной является запись его двоичной комбинации в виде многочлена F(x) некоторой фиктивной переменной x, а именно

.

Например, двоичная комбинация F = 1010011 семиразрядного циклического кода (7, 4) представляется полиномом



F(x) = 1x6+0x5+1x4+0x3+0x2+1x1+1x0 = x6+x4+x+1  1010011,

где стрелка обозначает соответствие двух записей.

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

При умножении полиномов старшая степень произведения может быть больше n-1. Для того, чтобы остаться в рамках n-разрядной комбинации циклического кода вводится операция умножения по модулю двучлена



F1(x)F2(x) [mod (xn+1)] = Rem [F1(x)F2(x)/(xn+1)],

где Rem - остаток от деления произведения F1(x)F2(x) на двучлен xn+1.

3.1.2. Построение циклического кода основано на использовании образующего полинома P(x). Образующий полином выбирается в разложении двучлена xn+1 на неприводимые многочлены. Старшая степень образующего полинома определяется числом контрольных символов k, а число ненулевых членов полинома P(x) должно быть больше или равно минимальному кодовому расстоянию d.

Циклический код (n,m) можно описать полно и компактно с помощью образующей матрицы в канонической форме [1, 2]



Fm,n = Im Rm,k, (3.1)

где Im - единичная квадратная матрица размерности mm, у которой на главной диагонали расположены единицы, а все остальные элементы равны нулю;



Rm,k - матрица контрольных символов размерности mk.

Строки матрицы Rm,k должны удовлетворять двум условиям:

1) содержать не менее d-1 единичных символов;

2) отличаться друг от друга не менее чем в d-2 разрядах.

Матрица контрольных символов Rm,k находится следующим формальным приемом. Единица с рядом нулей делится на образующий полином, записанный в виде двоичной последовательности. В процессе деления определяются m промежуточных остатков деления. Эти остатки, записанные в обратном порядке, образуют строки матрицы контрольных символов.

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

3.1.3. Вторым способом описания циклического кода является проверочная матрица. Она может быть представлена или в канонической форме или в циклической форме.

Проверочная матрица в канонической форме имеет вид



Hk,n = RТm,kIk = Qk,mIk, (3.2)

где RТm,k = Qk,m - транспонированная матрица контрольных символов, построенная на позициях информационных символов;



Ik - единичная квадратная матрица ранга k, построенная на позициях контрольных символов.

Проверочная матрица Hk,n используется для обнаружения и исправления ошибок в кодовой комбинации на приемной стороне. Строки проверочной матрицы дают состав проверок на четность:



j = 1,…,k , (3.3)

где dk-j - результат j-й проверки на четность;



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

bn-i - разряды комбинации циклического кода;

- знак суммирования по модулю 2.

Двоичная последовательность D=dk-1dk-2...d1d0, составленная из результатов проверок на четность, называется синдромом или опознавателем ошибки. Синдром можно представлять в виде полинома



D = dk-1dk-2...d1d0  D(x) = dk-1xk-1+…+d1x1+d0x0.

Если синдром состоит из одних нулей, то комбинация циклического кода считается безошибочной. Ненулевая величина синдрома (D 0) говорит о наличии ошибок.

На практике широко применяется циклическая форма проверочной матрицы

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



,

где hi - двоичные символы (0 или 1). Остальные строки получаются циклическим сдвигом вправо первой строки.

Вид первой строки проверочной матрицы определяется проверочным полиномом и находится следующим образом. Полином H(x) представляется в виде кодовой комбинации H=hmhm-1...h1h0. Запись этой комбинации в обратном порядке и приписывание к ней справа k-1 нулевых символов дает первую строку проверочной матрицы H*k,n.

Пример 1. Пусть циклический код (15, 6) задается образующим полиномом P(x) = x9+x6+x5+x4+x+11001110011 из разложения двучлена x15+1. Требуется составить образующую и проверочную матрицы данного кода, а также оценить его корректирующую способность.

Разделим единицу со многими нулями на образующий полином



Выписывая полученные остатки (подчеркнуты волнистой линией) снизу вверх (в обратном порядке), получим матрицу контрольных символов Rm,k



и согласно (3.1) образующую матрицу Fm,n .

Так как строки образующей матрицы имеют минимальный вес (число единиц) W = 6, то минимальное кодовое расстояние кода (15, 6) d=W=6. Найдем корректирующую способность кода на основании оценок Хемминга для минимального кодового расстояния:

где r и s - кратности (число) обнаруживаемых и исправляемых ошибок соответственно. Отсюда следует, что циклический код при d=6 позволяет или только обнаруживать ошибки кратности r=5, или одновременно обнаруживать ошибки кратности r=3 и исправлять ошибки кратности s=2.

Согласно (3.2) проверочная матрица в канонической форме имеет вид







Строки проверочной матрицы H9,15 дают состав проверок на четность, например:







- - - - - - - - - - - - - - - -

.

Составим проверочную матрицу H*9,15 в циклической форме. Разделив двучлен x15+1 на образующий полином, найдем проверочный полином



.

Записывая кодовую комбинацию Н=1001111 проверочного полинома в обратном порядке и приписывая к ней справа (к-1)=8 нулевых символов, получим первую строку матрицы Н*9,15 . Остальные строки получаются циклическим сдвигом вправо первой строки. В результате проверочная матрица в циклической форме будет иметь вид



Согласно матрице , состав проверок на четность принимает вид



;

;

- - - - - - - - - - - - - - - -

.

3.2. Методы обнаружения и исправления ошибок

3.2.1 На выходе канала связи ошибочная комбинация циклического кода может быть представлена как



,

где F - безошибочная комбинация;



L=ln-1ln-2...l1l0 - двоичная последовательность (комбинация ошибки) длиной n, содержащая единицы только в тех разрядах, которые искажены;

F (x) и - кодовые полиномы;

L(x) - полином ошибок.

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

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

F (x) = 0 [mod P(x)] или ; (3.3)

б) при умножении на проверочный полином дают тождественный нуль по модулю двучлена (xn+1), т.е.



или . (3.4)

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



. (3.5)

В случае использования свойства проверочного полинома (3.4) вычисляется синдром ошибок длиной n



.(3.6)

В декодирующих устройствах соотношения (3.5) и (3.6) реализуются вычислителем синдрома. Если синдром , это свидетельствует о наличии ошибок в принятой комбинации. Число возможных ненулевых синдромов M=2k-1. Если полиному ошибок L(x) соответствует индивидуальный синдром D(x), то по вычисленному синдрому можно определить полином ошибок и исправить принятый кодовый полином путем его сложения по модулю 2 с полиномом ошибок:



F(x) = F'(x) L(x). (3.7)

Если разным ошибкам отвечает один и тот же синдром, то ошибки не различаются, их можно только обнаружить.

3.2.2. При анализе и синтезе декодирующих устройств вместо (3.5) набор синдромов удобно получать непосредственно из проверочной матрицы в канонической форме. В матрице Hk,n i-столбец представляет собой синдром одиночной ошибки в bn-i -разряде кодовой комбинации. Остальные синдромы находят поразрядным суммированием по модулю 2 столбцов проверочной матрицы Hk,n в различных сочетаниях.

Cиндром (3.6) также удобно находить из проверочной матрицы в циклической форме. Однако для этого матрицу H*k,n нужно достроить, циклически сдвигая вправо ее строки до квадратной матрицы H*n,n ранга n . Тогда столбцы матрицы H*n,n представляют собой n-разрядные синдромы одиночных ошибок в соответствующих им разрядах кодовой комбинации. Остальные синдромы находят подобно матрице Hk,n.



Пример 2. Найдем синдром одиночной ошибки в старшем разряде циклического кода (15, 6) из примера 1.

Достроим матрицу H*9,15 до квадратной формы, циклически сдвигая вправо ее строки:



Первый столбец матрицы дает синдром одиночной ошибки в


разряде b14 :

D14,13=d14d13.....d0=100000000100111D14(x)=x14+x5+x2+x+1.

Синдром двойной ошибки, например в разрядах b14 и b13, имеет вид






D14,13=D14D13=
3.2.3. Рассмотрим способы исправления ошибок по синдрому. Пусть код (n,m) может исправлять все ошибки с кратностью s включительно. Тогда общее число исправляемых ошибок равно числу индивидуальных синдромов:

. (3.8)

Для исправления ошибок по (3.7) нужно знать полином L(x). Он формируется специальной решающей схемой, называемой селектором синдромов. Возможны два способа определения полинома ошибок - параллельный и последовательный.

При параллельном определении полинома ошибок селектор настраивается на N синдромов и формирует на выходе соответствующие им полиномы ошибок. Такой селектор представляет собой комбинационную схему, с выхода которой снимается кодовая комбинация ошибок Lj при подаче на вход кодовой комбинации синдрома Dj, j=1,2,...,N.

Сложность селектора синдромов определяется количеством N селектируемых синдромов. Число селектируемых синдромов для некоторых n и s, рассчитанное по соотношению (3.8), приведено в табл. 3.1.

Таблица 3.1

Длина кода n

15

31

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

1

2

3

1

2

3

Число селектируемых синдромов N

15

120

575

31

496

4991

Из табл. 3.1 видно, что сложность селектора синдромов очень быстро возрастает с ростом n и s. В результате даже при относительно малой кратности исправляемых ошибок селектор становится практически нереализуемым.

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

где Dj(x) и Di(x) - синдромы полиномов ошибок Lj(x) и Li(x); q - число сдвигов, q=0,1,2,...,n-1.

Таким образом, в результате циклического сдвига синдрома Di(x) на q шагов влево (в сторону старших разрядов) образуется синдром Dj(x).

Из множества N индивидуальных синдромов можно выделить T базовых синдромов:



. (3.9)

Остальные N-T синдромов приводятся к базовым при помощи операции циклического сдвига. Эти базовые синдромы называют корректорами D*j(x), j=1,2,...,T.

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

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

Отсутствие совпадения с корректорами при изменении q от 0 до n-1 говорит о наличии обнаруженных, но неисправляемых ошибок.

Число селектируемых синдромов-корректоров D*(x) для некоторых n и s, рассчитаное по соотношению (3.9), приведено в табл. 3.2.

Таблица 3.2



Длина кода n

15

31

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

1

2

3

1

2

3

Число селектируемых синдромов Т

1

15

106

1

31

466

Из сравнения табл.3.1 и 3.2 следует, что при последовательном определении полинома ошибок число селектируемых синдромов, а следовательно, и сложность селектора значительно меньше, чем при параллельном определении. Тем не менее при исправлении многократных ошибок сложность селектора и в данном случае остается чрезмерной. Поэтому область применения декодирования по синдрому ограничена в основном кодами с исправлением одиночных и двойных ошибок.

3.2.4. Техническую реализацию процесса исправления и обнаружения ошибок при последовательном декодировании облегчает метод модификации сдвигаемого синдрома. При этом для определения искаженных разрядов не требуется фиксации вида корректора, c которым совпал опознаватель ошибок.

Как правило, исправление ошибок начинается со старшего (n-1)-го разряда принятой комбинации путем циклического сдвига вычисленного синдрома. При совпадении через q тактов сдвигаемого синдрома с одним из корректоров осуществляется исправление ошибки в (n-1-q)-м разряде. Затем после исправления ошибки на (q+1) такте производится модификация синдрома таким образом, чтобы он соответствовал полиному оставшихся неисправленных ошибок (полиному ошибок, у которого двоичный символ ln-1-q=0). Другими словами, синдром s-кратной ошибки переводится в синдром (s-1)-кратной ошибки.

Циклический сдвиг модифицированного синдрома продолжается.При его совпадении с одним из корректоров через v тактов после модификации осуществляется исправление ошибки в (n-1-q-v)-м разряде принятой комбинации и производится следующая модификация синдрома.

Процесс исправления ошибок заканчивается через n тактов сдвига. На (n-1)-м такте проверяется состояние вычислителя синдрома. Нулевой синдром в вычислителе свидетельствует об исправлении ошибок. Если синдром не равен нулю, то это означает, что в принятом кодовом полиноме имеют место обнаруживаемые, но неисправляемые ошибки.

Наиболее просто задача модификации синдрома решается при исправлении однократных ошибок и обнаружении ошибок более высокой кратности (s=1, r=d-2). В этом случае достаточно после исправления ошибки обнулить ячейки вычислителя синдрома.

следующая страница >>


izumzum.ru