разрешенная комбинация циклического кода

Электронные средства сбора, обработки и отображения информации

Оглавление

Помехоустойчивое кодирование

Понятие корректирующего кода

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

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

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

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

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

Различают разделимые и неразделимые блоковые коды.

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

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

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

Общие принципы использования избыточности

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

— случаев безошибочной передачи;

— ·(-1) случаев перевода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам;

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

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

К_обн .

Рассмотрим, например, обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (п=k+1). Общее число выходных последовательностей составит , то есть вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество комбинаций, содержащих четное число единиц (или нулей). При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого четного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть обнаруженных ошибок составляет:

К_обн .

Пример кодирующего устройства с проверкой на четность показан на рис.

Основные параметры корректирующих кодов

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

Рассмотрим суть этих параметров.

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

Относительной избыточностью корректирующего кода называют величину

_отн

_отн.

Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы. Ее еще называют относительной скоростью передачи информации.

Если производительность источника равна Н символов в секунду, то скорость передачи после кодирования этой информации будет равна

поскольку в последовательности из п символов только k информационных.

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

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

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

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

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

В безызбыточном коде все комбинации являются разрешенными, =1. Достаточно только исказиться одному символу, и будет ошибка в сообщении.

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

Доказательство. Возьмем значность кода п=3. Возможные комбинации натурального кода образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Ошибки здесь не обнаруживаются и не исправляются, так как =1. Если =2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию.

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

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

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

+1.

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

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

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

Доказательство. Пусть, как и в предыдущем примере, п=3. Примем разрешенные комбинации 000 и 111 (кодовое расстояние между ними равно 3). Разрешенной комбинации 000 поставим в соответствие подмножество запрещенных комбинаций 001, 010, 100. Эти запрещенные комбинации образуются в результате возникновения единичной ошибки в комбинации 000.

Аналогично разрешенной комбинации 111 необходимо поставить в соответствие подмножество запрещенных комбинаций 110, 011, 101. Если сопоставить эти подмножества запрещенных комбинаций, то очевидно, что они не пересекаются:

В общем случае исправляемые ошибки кратности связаны с кодовым расстоянием соотношением

=2+1. (2.1)

где — сочетание из п элементов по t (число возможных ошибок кратности t на длине п-разрядной комбинации).

Если, например, п=7, =1, то из (2.1)

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

Групповой код с проверкой на четность

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

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

.

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

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

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

Проверочные символы располагаются следующим образом:

;

.

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

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

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

Коды с постоянным весом

Весом называется число единиц, содержащихся в кодовых комбинациях.

В коде «3 из 7» возможных комбинаций сто двадцать восемь (=128), а разрешенных кода только тридцать пять. Относительная избыточность _отн = 0,28.

Схема устройства определения веса комбинаций кода «3 из 7» приведена на рис. 2.6.

Циклические коды

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

— комбинация циклического кода;

— также комбинация циклического кода.

Например, комбинация 1001111 (п=7) будет представлена многочленом

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

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

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x) с приведением подобных членов по модулю 2:

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

Часто в качестве полинома, на который осуществляется деление, берется полином G(x)=+1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.

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

Число разрядов регистра выбирается равным степени образующего полинома.

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

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

В табл. 2.3 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011. п=7, k=4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.

Свойства циклического кода:

1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;

2) циклический код с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;

Источник

Алгоритмы сети Ethernet/Fast Ethernet

Циклические коды (CRC)

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

Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) или их корней. Порождающий полином имеет вид

и кодированного сообщения

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

1) информационная часть сообщения записывается в виде полинома:

В рассматриваемом примере k=4 и для сообщения 0111 получается

u(x) x 3 = (x 2 + x + 1) x 3 = x 5 + x 4 + x 3

3) полученный многочлен делится на g(x) :

где c(x) – полином-частное с максимальной степенью (k—1) ;

R(x) – полином-остаток с максимальной степенью (r-1) ;

– обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ). Кодированное сообщение представляется в виде

Таким образом, в этом случае

Передаваемое кодированное сообщение в обычной двоичной форме имеет вид

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

Источник

Циклические коды

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

Рубрика	Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид	доклад
Язык	русский
Дата добавления	20.03.2015
Размер файла	53,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

АО «Казахская академия транспорта и коммуникаций имени М. Тынышпаева»

Кафедра «Радиотехника и телекоммуникации»

по дисциплине «Элементы теории информации»

на тему: Циклические коды

1. Определение циклических кодов

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

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

4. Укороченные циклические коды

5. Обнаружение и исправление пачек ошибок

Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.

Данный доклад содержит информацию о циклических кодах: определение, операции производимые над ними, а также принципы построения циклических кодов. циклический код комбинация

В настоящее время широчайшее распространение в телекоммуникациях получили циклические коды. На практике, как правило, применяются циклические коды, корректирующие ошибки невысокой кратности t 2.

1. Определение циклических кодов

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

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

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

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

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

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

— цифры данной системы счисления;

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

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

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

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

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

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

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

Двоичная запись P(x)

Построение разрешенной кодовой комбинации циклического кода сводится к следующему:

1. Представляем информационную часть кодовой комбинации длиной k в виде полинома Q(x).

3. Делим многочлен Q(x) xr на образующий полином Р(x), степень которого равна r. В результате деления образуется остаток R(x).

4. Разрешенная кодовая комбинация циклического кода имеет следующий вид:

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

Для определения местоположения ошибки в циклическом коде существует ряд методов, основанных на анализе «синдрома» R(x).

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

4. Укороченные циклические коды

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

Если, например, необходимо исправить единичные ошибки при k = 5, то нельзя взять образующий многочлен третьей степени, поскольку он даст только семь остатков, а общее число разрядов получится равным 8.

Следовательно, необходимо брать многочлен четвертой степени и тогда n= 15. Такой код рассчитан на 11 информационных разрядов.

5. Обнаружение и исправление пачек ошибок

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

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

Коды Рида-Соломона способны исправлять несколько пачек ошибок.

Особенности декодирования циклических кодов, исправляющих пакеты ошибок, рассмотрены далее на примере кодов Файра.

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

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

Подобные документы

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

доклад [51,6 K], добавлен 19.10.2014

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

реферат [136,4 K], добавлен 09.02.2010

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

лабораторная работа [69,1 K], добавлен 13.04.2013

Кодирование сигнала и структурированные последовательности. Определение линейного группового кода с повторением; длина кодового слова, количество информационных символов. Определение минимального расстояния Хэмминга кода, порождаемого матрицей Адамара.

контрольная работа [407,0 K], добавлен 12.11.2012

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

лабораторная работа [1,6 M], добавлен 30.11.2013

реферат [195,1 K], добавлен 11.02.2009

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

реферат [66,4 K], добавлен 01.11.2011

Источник