Itnewsrussia.ru

Анализ современных технологий

Анализ возможности использования корректирующих кодов

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

(2.12)

гдеn - количество символов в кодовой комбинации, представляемой многочленом (значность кода);

x - фиктивная переменная;

а0, а1, а2, …- коэффициенты, принимающие значения 0 или 1.

Например, кодовой комбинации 1001000011 соответствует многочлен . Представление комбинаций в виде многочленов позволяет все действия над комбинациями свести к действиям над многочленами, с которыми можно производить все алгебраические операции. Особенностью является то, что сложение и вычитание коэффициентов производится по модулю два. В качестве примера произведем все основные операции с многочленами

и .

Название "циклический код" определяется основным свойством этих кодов, состоящим в том, что циклический сдвиг символов разрешенной комбинации на один символ влево образует разрешенную комбинацию. Заметим, что циклический сдвиг комбинации эквивалентен умножению ее многочлена на x с последующим переносом коэффициента при высшей степени x в начало комбинации:

(2.13)

Приведем здесь определение циклических кодов , которое основано на представлении двоичных кодов в виде многочленов: циклическим (n, k) кодом называется код, множество кодовых комбинаций которого представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый образующий многочлен р (x) степени q=n-k.

Исходя из этого определения, для формирования комбинации циклического кода F (x) достаточно исходную комбинацию безызбыточного кода G (x) умножить на образующий многочлен p (x)

(2.14)

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

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

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

(2.15)

где Q (x) - целая часть частного.

Искомый многочлен циклического кода имеет вид:

(2.16)

Здесь информационные символы представлены коэффициентами при x в степени q, и выше, а проверочные - коэффициентами при x в степени q-1 и ниже. Многочлен (2.16) представляет разрешенную комбинацию циклического кода и в соответствии с определением делится на образующий многочлен р (х) без остатка.

Действительно,

(2.17)

Здесь учитывалось (2.15) и то, что при сложении по модулю два двух одинаковых многочленов в результате получается 0.

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

Таблица 3

q

Вид неприводимого многочлена

N=2q-1

1

1

2

3

3

7

4

15

5

31

6

63

7

127

8

256

9

511

10

1023

Перейти на страницу: 1 2 3 4 5 6 7

Популярное:

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