Размещено на http://www.allbest.ru/

Некоммерческое акционерное общество

"АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ"

Кафедра инженерной кибернетики

РАСЧЕТНО - ГРАФИЧЕСКАЯ РАБОТА № 1

По дисциплине: "ОСиПИ"

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

Алматы 2014



Построение циклического (n,k)-кода

Цель лабораторной работы

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

Основные сведения о циклических кодах

Двоичный код - сочетание единиц и нулей, соответствующих определенному символу или цифре, которую надо передать.

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

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

Одним из методов борьбы с ошибками - является введение избыточности (добавляются проверочные разряды). Например, при 5 - элементном простом коде МТК-2 число кодовых комбинаций 2⁵ = 32, а при избыточном кодировании с одним добавочным разрядом число кодовых комбинаций равно 2⁶ = 64.

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

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

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

Для простых (безызбыточных) кодов d_min = 1.

Минимальное кодовое расстояние d_min связано с числом или кратностью обнаруживаемых и исправляемых t ошибок следующим образом:

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

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

Избыточностью кода называется отношение , где r - число проверочных разрядов; n - длина кодовой комбинации, а называют скоростью кода.

Для исправления однократной ошибки (t =1) число проверочных разрядов должно отвечать неравенству:

log₂(n + 1) или 2^r(n + 1). (1)



В общем случае, при исправлении ошибок кратности t, число проверочных разрядов должно отвечать неравенству:

где .

комбинация циклический код ошибка

Алгоритм формирования комбинаций циклического (n, k)-кода

При построении двоичных циклических кодов кодовые комбинации длины n принято представлять в виде полиномов степени (n -1):

F(x) = a_n-1x^n-1 + a_n-2x^n-2 + ...+ a₁x + a₀,

где a₀, a₁, ...,a_n-1 - коэффициенты, принимающие значения 0 или 1.

Например, кодовую комбинацию 1001101 можно записать в виде:

F(x) = x⁶ + x³ + x² + 1.

Поэтому циклические коды часто называют полиномиальными кодами.

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

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

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

Рассмотрим построение комбинации систематического циклического (n,k)-кода. Будем полагать, что порождающий многочлен задан. Алгоритм формирования циклического кода будет следующим:

G(x)x^{(n - k)}, то есть информационный полином G(x) умножается на x в степени равной степени порождающего многочлена r = (n - k). Умножение полинома на x^r означает сдвиг на r разрядов влево.

, то есть произведение G(x)x^(n-k) делится на порождающий многочлен P(x) и определяется частное Q(x) и остаток от деления R(x). Степень R(x) всегда ниже степени порождающего многочлена.

F(x) = G(x)x^(n-k) R(x), то есть комбинация циклического кода строится как совокупность информационных элементов и приписанных к ним со стороны младших разрядов элементов остатка (проверочных элементов).

Рассмотрим пример построения циклического кода для информационного полинома вида G(x) = x⁴ + x² + x. Этот информационный полином G(x) соответствует двоичной кодовой комбинации 10110.

Пусть порождающий многочлен имеет вид: P(x) = x⁴ + x + 1. В соответствии с неравенством (1) максимальная длина кодовой комбинации циклического кода n = 2^r - 1 равна 15 (полный код). Однако, на практике часто выбирают длину комбинации n₁ < 2^r - 1. Образующийся при этом циклический код называют укороченным. Следует иметь ввиду, что укорочение происходит за счет уменьшения числа информационных разрядов k.

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

В нашем примере разрядность исходного кода (информационного полинома G(x)) равна 5. Число проверочных разрядов определяется степенью порождающего многочлена (у нас - это 4). В итоге разрядность комбинации циклического кода равна 9, то есть мы получим укороченный код (9, 5).

Выполним первую операцию построения систематического циклического кода - умножения на x⁴ информационного полинома G(x). Получим полином G(x)x⁴ = x⁸ + x⁶ + x⁵.

Умножению информационного полинома G(x) на x⁴ соответствует добавление справа четырех нулей к двоичному представлению G(x), т.е. 101100000.

Вторая операция - деление G(x)x⁴ на порождающий многочлен P(x):

Здесь операция вычитания заменяется операцией сложения по mod 2. Операция суммирования по mod 2 выполняется по следующему алгоритму:

1 1 = 0; 0 0 = 0; 1 0 = 1; 0 1= 1



Та же операция деления в двоичном коде имеет вид:

Третья операция - построение комбинации циклического кода F(x):

F(x) = G(x)x^(n-k) R(x) =

Полученный результат в двоичном коде имеет вид:

Сделаем проверку полученного циклического кода, представленного полиномом F(x), делением этого полинома на порождающий многочлен P(x). Остаток от деления должен быть нулевым.

Та же операция в двоичном коде:



Итак, для заданного информационного кода G(x) разрядностью 5 получен укороченный циклический код разрядностью 9, т. е. код (n, k) = (9, 5). Минимальное кодовое расстояние (расстояние Хэмминга) для этого кода равно d_min = 3, то есть он позволяет обнаруживать все ошибки кратностью 2 или исправлять однократные ошибки (t = 1). В режиме обнаружения данный код может обнаруживать и часть ошибок более высокой кратности.

Общее число кодовых комбинаций рассматриваемого кода N_общ = 2⁹ = 512; число разрешенных кодовых комбинаций N_разр = 2⁵ = 32; число запрещенных кодовых комбинаций N_запр = N_общ - N_разр = 480.

Избыточность данного кода равна а кодовая скорость -

Для получения всех ненулевых разрешенных комбинаций (для кода (9,5) - это 2⁵-1=31) составляют порождающую матрицу называемую также образующей или производящей матрицей, которая состоит из единичной матрицы размерности k,k (для кода (9,5) - это 5,5) и матрицы проверочных элементов размерности k,n-k (для кода (9,5) - это 5 , 4).

Единичная матрица имеет вид:



Для нахождения строк матрицы проверочных элементов выполняется деление многочлена вида на порождающий многочлен. Полученные на каждом шаге деления остатки и являются строками проверочной матрицы . Пример получения проверочных элементов для кода (9,5) и порождающего многочлена P(x)=10011 имеет вид:

Порождающая матрица для рассматриваемого примера будет иметь вид:

Каждая строка этой матрицы является разрешенной кодовой комбинацией кода (9,5). Для получения остальных разрешенных кодовых комбинаций необходимо каждую строку матрицы сложить по mod2 с каждой строкой, затем с двумя строками, с тремя и т.д.Например, сложение первой строки со второй даст разрешенную комбинацию вида: 110001110, сложение всех пяти строк также даст разрешенную комбинацию вида: 111110111.

Для определения минимального кодового расстояния циклического кода (n,k) следует составить его проверочную матрицу , которая получается путем транспонирования (замены местами строк и столбцов) матрицы проверочных элементов с последующим дописыванием справа элементов единичной матрицы размерностью (n-k). В нашем случае проверочная матрица циклического кода (9,5) имеет вид:

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

При наличии двух одинаковых столбцов в проверочной матрице минимальное кодовое расстояние =2, а при их отсутсутствии- и определяется путем перебора.

Для кода (9,5) минимальное число столбцов, дающее при построчном суммировании по mod2 нулевой столбец, равно трем (эти столбцы отмечены знаком (*) в матрице ). Следовательно, минимальное кодовое расстояние циклического кода (9,5) =3, что позволяет ему гарантированно исправить однократную или обнаружить двукратную ошибку.



Структурная схема кодирующего устройства

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

Число ячеек памяти (разрядов) в регистре сдвига равно степени порождающего многочлена P(x) (в нашем случае - 4, T1 - младший разряд, T4 - старший разряд).

Количество сумматоров по mod 2 равно весу порождающего многочлена P(x) минус единица. В нашем примере вес P(x) равен 3, значит число сумматоров по mod 2 равно двум.

Сумматоры по mod 2 ставятся перед ячейками памяти, соответствующими ненулевым членам порождающего многочлена P(x), исключая его старшую степень.

Структурная схема кодирующего устройства для кода (9,5) и порождающего многочлена P(x)= x⁴ + x + 1, построенная в соответствии с указанными правилами, приведена на рис.1

Рис.1. Структурная схема кодера циклического кода (9,5) для



В представленной схеме кодера имеется 4 триггера: T₁, T₂, T₃ и T₄, в качестве ячеек памяти, и 2 сумматора по mod 2: C₁ и C₂, а также- два ключа, роль которых выполняют схемы И₁ и И₂, и схема ИЛИ. Схема тактируемая.

Схема кодера работает следующим образом.

Информационный полином G(x) поступает на сумматор C₂, что реализует операцию умножения G(x) на х⁴. Получаемое на выходе сумматора C₂ произведение х⁴G(x) далее делится на порождающий многочлен P(x), что реализуется с помощью обратных связей через схему И₁. Пока поступает информационная кодовая комбинация G(x), то есть в нашем случае - с 1^го по 5^й такты, схема И₁ открыта, а схема И₂ закрыта вследствие чего информационные элементы поступают на выход кодера. После k тактов, где k - число информационных разрядов, ключ И₁ размыкается, а ключ И₂ замыкается и с регистра сдвига на выход кодера считывается остаток от деления R(x). В последующие такты с 6^го по 9^й через схему И₂ остаток от деления выводится в канал связи. Состояние триггеров на каждом такте работы схемы для показано в табл.1.

Подробнее описание работы устройства кодирования приведено в приложении.

Таблица 1

Такты	Вход G(x)	T1	T2	T3	T4	Выход F(x)
1	1	1	1	0	0	1
2	0	0	1	1	0	0
3	1	1	1	1	1	1
4	1	0	1	1	1	1
5	0	1	1	1	1	0
6		0	1	1	1	1
7		0	0	1	1	1
8		0	0	0	1	1
9		0	0	0	0	1



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

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

F(х)Н(х)=Е(х),

где Е(х) - полином ошибок.

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

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

Для обнаружения ошибок в принятой кодовой комбинации Н(х) следует разделить Н(х) на порождающий многочлен Р(х). Результат деления укажет на наличие или отсутствие ошибки в принятой кодовой комбинации Н(х). Если деление дает нулевой остаток, то ошибки отсутствуют или не обнаружены. Если же в результате деления полинома Н(х) на порождающий многочлен Р(х) остаток R'(х) отличен от нуля , то это означает что принятая кодовая комбинация Н(х) содержит ошибки (рис 2).



Рис.2. Схема выявления ошибок в принятой кодовой комбинации H(x)

Вид ненулевого остатка R'(x), называемого синдромом ошибки S(х), имеет однозначное соответствие с ошибочным разрядом и видом полинома однократной ошибки Е(х) для всех кодовых комбинаций Н(х) циклического кода. Например, для циклического кода (9,5) при заданном порождающем многочлене P(x)= x⁴ + x + 1 остаток R'(x) всегда будет иметь вид S(х)=0011, если ошибка возникла в пятом разряде входной кодовой комбинации, т.е. в младшем информационном разряде, независимо от вида переданной кодовой комбинации F(х).

Следует отметить, что остаток R'(x), получаемый при делении полинома Н(х), на порождающий многочлен Р(х), имеет такой же вид, как и остаток от деления Е(х) на Р(х), поскольку полином F(х) делится на Р(х) без остатка.

Кратность обнаруживаемых ошибок в принятой кодовой комбинации циклического кода определяется минимальным кодовым расстоянием d_min этого кода. Для циклического кода (9,5) значение d_min=3, что обеспечивает гарантированное обнаружение всех однократных и двукратных ошибок. Кроме того, код позволяет обнаруживать часть ошибок более высокой кратности, начиная с веса, равного d_min и более. Код не обнаруживает ошибки, если полином ошибки имеет вид разрешенной кодовой комбинации.

Для исправления однократной ошибки в принятой кодовой комбинации Н(х) необходимо определить место ошибки. С этой целью также производится деление полинома Н(х) на порождающий многочлен Р(х). Для определенности вновь обратимся к коду (9,5). Если на 9^ом такта в регистре-делителе (декодирующем регистре) будет зафиксирована хотя бы одна единица, то деление продолжается до тех пор, пока в регистре-делителе не будет зафиксирована "особая" кодовая комбинация. Вид этой комбинации зависит только от вида порождающего многочлена Р(х) и длины n комбинации циклического кода F(х), причем находится "особая" кодовая комбинация как остаток от деления хⁿ на P(x) [3]. В нашем случае, для кода (9,5) и порождающего многочлена Р(х)=х⁴+х+1 "особая" кодовая комбинация, всегда имеет вид 1010.

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

Циклический код (9,5) гарантированно исправляет только однократные ошибки. Ошибки более высокой кратности код (9,5) не исправляет.

Заметим также, что деление полинома Н(х) на многочлен Р(х) и считывание информации из буферного регистра после 9^го такта целесообразно осуществлять под действием "быстрых" тактовых импульсов. Это позволит без задержки принять из канала связи и обработать следующую кодовую комбинацию Н(х).



Декодирующее устройство циклического кода (9,5), обеспечивающее обнаружение ошибок

Структурная схема декодера, точнее- его декодирующего регистра, строится по тем же правилам, что и кодера. В состав декодера циклического кода (9,5), обнаруживающего все однократные и двукратные, а также ряд ошибок более высокой кратности в принятой кодовой комбинации Н(х), входят: буферный регистр на 9 разрядов, декодирующий регистр (регистр-делитель), схема ИЛИ-НЕ, схема И, а также - управляющее устройство, замыкающее ключ К после 9^го такта (на схеме устройство не показано) (рис.3). На вход декодирующего регистра поступает кодовая комбинация H(x), которая делится на порождающий многочлен P(x).По окончании деления, после 9^ти тактов, в триггерах Т1Т4 декодирующего регистра декодера записывается и остаток от деления. Если при этом хотя бы один из триггеров Т1Т4 находится в единичном состоянии, то это означает, что в принятой кодовой комбинации Н(х) имеется ошибка. Для обнаружения ошибки деление продолжается до 14^го такта включительно, но уже "быстрыми" тактовыми импульсами и на каждом из этих тактов сигналы с выходов триггеров Т1Т4 поступают на вход схемы ИЛИ-НЕ. На выходе схемы ИЛИ-НЕ формируется нулевой сигнал, который при замкнутом ключе К поступает на второй вход схемы И. На первый же вход этой схемы И поступает кодовая комбинация Н(х) из буферного регистра декодера циклического кода. Под действием нулевого сигнала с выхода схемы ИЛИ-НЕ схема И запирается и кодовая комбинация Н(х) не поступает из буферного регистра на выход схемы декодера.

Если же все триггеры Т1Т4 декодирующего регистра декодера обнулены после 9^го такта, то на выходе схемы ИЛИ-НЕ с 10^го по 14^й такт имеет место единичный сигнал. Тогда схема И пропускает на выход декодера безошибочно принятую (или с необнаруженными ошибками) кодовую комбинацию из буферного регистра, причем потребителю направляются первые пять разрядов, составляющих информационную кодовую комбинацию G(х).

Наглядной иллюстрацией работы декодирующего регистра декодера могут служить таблицы состояний его триггеров. В качестве примера такие таблицы даны для комбинации циклического кода F(х)=101101111 в случае, когда ошибок нет (табл.2); и в случае, когда ошибка произошла во 2^ом разряде (табл.3); - во 2^м и 3^м разрядах (табл.4);- в 1^м , 3^м и 5^м разрядах (табл.5) и- в 1^м ,4^м и 5^м разрядах (табл.6).



Заключение

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

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

При декодировании принятой n-разрядной кодовой комбинации опять производится деление на порождающий полином.

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

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



Список использованной литературы

Лидовский В.И. Теория информации. - М., "Высшая школа", 2002г. - 120с.

Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971.

Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования. - М.: Мир, 1978.

Колесник В. Д., Мирончиков Е. Т. Декодирование циклических кодов. - М.: Связь, 1968.

Мак-Вильямс Ф., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. - М.: Связь, 1979.

Размещено на Allbest.ru

...