Теоретические сведения. Лабораторная робота №6

Лабораторная робота №6

з курсу «Теорія інформації та кодування»

Тема: Построение циклических кодов с добавлением остатка от деления

Виконав: Старцев О. Є.

студент групи 1КСМ

Перевірив:

к.т.н., доцент Лєпа Є.В.

Херсон 2012

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

Теоретические сведения

Циклические коды – коды, в которых часть или все комбинации могут быть получены путем циклического сдвига одной или нескольких комбинаций кода. Для таких кодов характерно следующее.

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

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

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

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

n = n_и + n_к. (1)

Эти соотношения рассчитываются по формулам (рассматриваются далее) и представлены в приложении для минимального кодового расстояния d0 = 3.

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

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

1. Степень его должна быть не меньше числа контрольных разрядов. Для конкретного примера степень равна трем.

2. Многочленов этой степени всего два – 1011 и 1101.

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

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

Таким образом, можно взять любой из двух многочленов, например, 1011. Его можно представить в виде полинома

1011 = 1 * X³ + 0 * X² + 1* X¹ + 1 * X⁰

К (Х) = Х³ + Х +1 = 1011

Умножаем И (X) на одночлен той же степени, что и образующий многочлен. От умножения многочлена на одночлен степени n степень каждого члена многочлена повысится на n, что эквивалентно приписыванию n нулей со стороны младших разрядов многочлена. Так как степень выбранного неприводимого многочлена равна трем, то исходная информационная комбинация умножается на одночлен третьей степени

И (Х) Хⁿ = (Х³ + Х² +1)Х³ = Х⁶ + Х⁵ + Х³ = 1101000

Осуществляется эта процедура для того, чтобы впоследствии вместо этих нулей можно было записать корректирующие разряды. Значение корректирующих разрядов находят в результате деления И (X) Хⁿ на К(X):

Выполним такое же деление, но многочлены запишем в двоичной форме

(2)

где Q(X) – частное, а R(X) – остаток от деления И(X) на K(X).

Так как в двоичной арифметике 1 1 = 0, а значит и – 1 = 1, то можно при сложении двоичных чисел переносить слагаемые из одной части равенства в другую без изменения знака (если это удобно), поэтому равенство вида а b = 0 можно записать и как а = b, и как а – b = 0.

Все три равенства в данном случае означают, что либо и а и b равны 0, либо и а и b равны 1, т. е. имеют одинаковую четность.

Исходя из сказанного, выражение (2) можно записать как

(3)

и после переноса R(X) в левую часть равенства (2)

(4)

что для рассматриваемого примера даст

F(X) = (X³ + X² + X + 1)(X³ + X + 1) = (X³ + X² + 1) X³ + 1

или

F(X) = 1111 * 1011 = 1110000 + 001 = 1101001

Многочлен 1101001 и есть искомая комбинация, где 1101 – информационная часть, а 001 – контрольные символы.

Дата добавления: 2015-07-16