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

21553
знака
2
таблицы
1
изображение

АННОТАЦИЯ

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

этого образуюший полином P(x) равен :

 P(x)= x5 +x4 +x3 +x 2 +1 =111101.

6. Определим остаток R(x) от деления G(x)×x m на образующий по-

лином P(x)

x7+ x5 x5 +x4 +x3 +x 2 +1 10100000 111101

x7 +x6 +x5 +x 4 +x2 x2 +x +1  111101 111

x6 +x4 +x2 101010

x6 +x5 +x4 +x 3 +x 111101

x5 +x3 +x2 +x 101110

x5 +x4 +x3 +x 2 +1 111101

x4 +x+1 10011

 Остаток R(x)= x4+x+1 =10011.

7. Строим передаваемый кодовый пролином F(x) :

F(x)=xm G(x)ÅR(x)= x7+ x5+x4+x+1=0000000000000000000000010110011.

8. Пусть в принятом сообщении произошла ошибка в тридцать первом разряде,при зтом принятое кодовое сообщение имеет вид :

F¢(x)=F(x) Å E(x)= 1000000000000000000000010110011.

9. Разделим многочлен F1(x) соотвествующий полученной кодовой ком-бинации на образующий полином, при этом вес остатка (количество единиц в коде остатка) должен быть меньше или равен количеству ошибок W £S

1000000000000000000000010110011 111101

111101

111010

111101

111000

111101

101000

111101

101010

111101

101110

111101

100110

111101

110110

111101

101100

111101

100010

111101

111110

 111101

110010

111101

111111

111101

 100011

111101

11110

Сравниваем вес полученного остатка w с числом исправляемых ошибок

w>s .

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

разряд влево и повторяем п.9 пока w £ s.

a) 0000000000000000000000101100111 111101

111101

 100011

111101

111101

111101


Информация о работе «Кодовые комбинации на основе циклических кодов»
Раздел: Информатика, программирование
Количество знаков с пробелами: 21553
Количество таблиц: 2
Количество изображений: 1

Похожие работы

Скачать
28614
0
12

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

Скачать
23519
5
3

... выходного кода, граф-схему алгоритма работы основного декодирующего модуля с комментариями, объем и результаты тестового декодирования (например, в табличной форме) с подробными комментариями.   7. Быстрый кодер / декодер для циклических кодов Применение быстрого алгоритма в лабораторной работе не является обязательным для всех. Он может быть использован по желанию студентов или по прямому ...

Скачать
13104
1
4

... , если его длина n=qm-1 над GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена xn+1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются ...

Скачать
229704
44
52

... , работавших в области электротехники, заинтересовалась возможностью создания технологии хранения данных, обеспечивающей более экономное расходование пространства. Одним из них был Клод Элвуд Шеннон, основоположник современной теории информации. Из разработок того времени позже практическое применение нашли алгоритмы сжатия Хаффмана и Шеннона-Фано. А в 1977 г. математики Якоб Зив и Абрахам Лемпел ...

0 комментариев


Наверх