Кодовые комбинации на основе циклических кодов (45927)

Посмотреть архив целиком



АННОТАЦИЯ

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































СОДЕРЖАНИЕ


1. Введение ........................................................................................... 6

2. Постановка задачи .......................................................................... 7

3. Операции над циклическими кодами ............................................. 8

4. Принцип построения циклических кодов ....................................... 9

4.1. Получение кодовой комбинации добавлением остатка R(x) ...... 11

4.2. Получение кодовой комбинации умножением на образующий

полином .......................................................................................... 14

5. Разработка схемы алгоритма ........................................................... 15

6. Разработка текста программы ......................................................... 16

7. Результаты работы программы ....................................................... 21

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

Литература ........................................................................................ 23

Приложение № 1 ............................................................................... 24

Приложение № 2 ............................................................................... 30
















§ 1 Введение


Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим ( полиномиальным, кодом с циклическими избыточными проверками-ЦИП).

Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.

Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.

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

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

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

тивность при обнаружении и исправлении ошибок обеспечила им широеое применение на практике.

Циклические коды используются в ЭВМ при последовательной передаче данных .

















 2 Постановка задачи


Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки ( n=31 ,s=1) двумя

способами.

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



























 3 Операции над циклическими кодами

1. Сдвиг справа налево осуществляется путем умножения полинома на x:

G(x)=x4+x2+1  0010101;

G(x)x=x5+x3+x  0101010.

2. Операции сложения и вычитания выполняются по модулю 2 .

Они являются эквивалентними и ассоциативными :

G1(x)+G2(x)=>G3(x);

G1(x) -G2(x)=>G3(x);

G2(x)+G1(x)=>G3(x);

Пример:

G1(x)= x5 +x3+x;

G2(x)=x4 +x3 +1;

G3(x)=G1(x)  G2(x) = x5 +x4+x+1.

3. Операция деления является обычным делением многочленов, только вместо вычитания используется сложеное по модулю 2 :


G1(x)=x6+x4+x3 ;

G2(x)=x3+x2+1 .


x6+x4+x3 x3+x2+1

 x6+x5+x3 x3 +x2

x5 + x4

 x5 + x4 +x2

x2

то же в двоичном коде:

1011000 1101

1101 1100

1100

 1101

100

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











 4 Принцип построения циклических кодов


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

Чтобы понять принцип построения циклического кода,умножаем комбинацию простого k-значного кода Q(x) на одночлен xr ,а затем делина образующий полином P(x) , степень которого равна r. В результате умножения Q(x) на xr степень каждого одночлена, входящего в Q(x), повы-шается на r. При делении произведения xrQ(x) на образующий полином получается частное C(x) такой же степени, как и Q(x).Результат можно представить в вид

Q(x) xr R(x)

 = C(x) +  , (1)

P(x) P(x)

где R(x) - остаток от деления Q(x) xr на P(x).

Частное C(x) имеет такую же степень, как и кодовая комбинация Q(x) простого кода, поэтому C(x) является кодовой комбинацией этого же

постого k-значного кода. Следует заметить,что степень остатка не может быть больше степени образующего полинома, т.е. его наивысшая степень может быть равна (r-1). Следовательно, наибольшее число разрядов остатка R(x) не превышает числа r.

Умножая обе части равенства (1) на P(x) и произведя некоторые перестановки получаем :

F(x) = C(x) P(x) = Q(x) xr + R(x) (2)

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

быть получена двумя способами:

1) умножение кодовой комбинации Q(x) простого кода на одночлен xr

и добавление к этому произведению остатка R(x) , полученного в результате деления произведения Q(x) xr на образующий полином P(x);

2) умножения кодовой комбинации C(x) простого k-значного на образующий полином P(x).

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

они занимают k старших разрядов комбинации, а остальные (n-k) разрядов

отводятся под контрольные.

При втором способе образования циклических кодов информа-

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



















 4.1 Получение кодовой комбинации добавлением остатка R(x)


Построить циклический код для передачи 31 разрядной кодовой

комбинации с исправлением однократной ошибки ( n=31, s=1)

Решение.

1. Определим число контрольных разрядов - m :

m = log2 (n+1) = log2 (31+1) = 5.

2. Определим количество информационных разрядов k :

k = n-m = 26,

т.е получили (31, 26 ) - код .

3. Строим информационный полином,сответствующий информационному слову длиной k-бит:

G(x)=00000000000000000000000101= x2 +1.

4. Осуществлям сдвиг кода влево на m=n-k=5 разрядов т.е полином G(x) умножается на xm :

xm G(x)= (x2+1) x5= x7+ x5 =0000000000000000000000010100000.

5. Выбирается образующий многочлен-P(x) по таблице неприводимых многочленов. Для исправления одиночной ошибки (d0=3) образующий полином P(x) должен быть степени m=n-k=5 и количеством ненулевых членов не меньше минимального кодового расстояния d0 =3. Исходя из


Случайные файлы

Файл
30935.rtf
14884.rtf
18263-1.rtf
181163.rtf
_ 231 П.doc




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.