Простейшие корректирующие коды icon

Простейшие корректирующие коды



НазваниеПростейшие корректирующие коды
Дата конвертации22.11.2012
Размер176.93 Kb.
ТипДокументы
скачать >>>
1. /Корректирующие коды в системах передачи информации/POC9_11.DOC
2. /Корректирующие коды в системах передачи информации/POC9_12.DOC
3. /Корректирующие коды в системах передачи информации/POC9_21.DOC
4. /Корректирующие коды в системах передачи информации/POC9_31.DOC
5. /Корректирующие коды в системах передачи информации/POC9_32.DOC
6. /Корректирующие коды в системах передачи информации/POC9_33.DOC
7. /Корректирующие коды в системах передачи информации/POC9_34.DOC
8. /Корректирующие коды в системах передачи информации/POC9_41.DOC
9. /Корректирующие коды в системах передачи информации/POC9_LIT.DOC
10. /Корректирующие коды в системах передачи информации/PИC9_П.DOC
Г. А. Чернецкий Корректирующие коды в системах передачи информации учебное пособие новосибирск
Простейшие корректирующие коды
2 Циклические коды 1 Кодирование циклических кодов
3 Свёрточные коды 1 Свёрточные коды и их свойства
3. 3 Пороговое декодирование свёрточных кодов
3. 4 Итерационные алгоритмы порогового декодирования
3. 5 Реализация пороговых кодеков сверточных кодов
5. 1 Методика статистического анализа канала связи и устройств
Учебник для вузов/А. Г. Зюко, Д. Д. Кловский, М. В. Назаров, Л. М. Финк. М.: Радио и связь, 1986. 304 с
Приложение 1 Таблица многочленов циклических кодов бчх (TablСycle)

    1. Простейшие корректирующие коды


1.3.1 Код с четным числом единиц

Код с четный числом единиц является двоичным блочным кодом и образуется путем добавления к кодовому слову k-символьного кода одного избыточного символа так, чтобы количество единиц в новом -символьном слове было четным. В таблице 1.1 приведён пример кодирования пятизначного кода: k=5, n=6 .

Таблица 1.
1 Таблица кодирования





1

2

3

4

5

6

1

0

1

0

0

1

1

0

1

0

0

0

1

0

1

0

0

1

1

1

1

0

0

1

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

Если в канале связи ошибки независимы и вероятность искажения кодового символа равна , то согласно биномиальному закону распределения вероятность обнаружения ошибки равна

(1.21)

вероятность искажения кодового слова



вероятность необнаруженной ошибки

(1.22)


Коэффициент избыточности этого кода


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

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

(1.23)


разрешенных кодовых слов. Такого числа слов достаточно для помехоустойчивого кодирования всех кодовых слов 5-значного телеграфного кода.

Семизначный код 3/4 относится к неразделимым кодам с постоянным весом. В кодовом слове этого кода невозможно разделить символы на информационные и проверочные (избыточные). Обнаружение ошибок производится простым подсчетом единиц или нулей в принятой кодовом слове. Код обнаруживает все ошибки нечетной кратности и около 50% ошибок четной кратности. Ошибки не обнаруживаются, если в одном кодовом слове искажается одинаковое число единиц и нулей. Например, если в разрешенном слове 1011000 искажены первый и второй (или второй и третий и т.д.) кодовые символы, то кодовое слово превращается в другое разрешенное - 0111000 и т.д.

Вероятность необнаруженной ошибки для кода 3/4 в канале связи с независимыми ошибками равна



Избыточность кода g = r/n = 2/7  0,3. (1.24)

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


1.3.3 Инверсный код

Кодовые слова инверсного корректирующего кода образуются повторением исходного кодового слова (таблица 1.2). Если число единиц в исходном слове четное, оно повторяется в неизменном виде; если число единиц нечетное, то при повторении все символы исходного кодового слова инвертируются (нули заменяются единицами, а единицы - нулями).

Таблица 1.2 Таблица кодирования




k

r




1

2

3

4

5

6

7

8

9

10

a)

a)

б)

б)

1

0

0

1

0

1

1

0

1

1

1

0

1

0

0

0

1

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

1

0

1

1

1

0

0

1

а) - в исходном кодовом слове четное число единиц,

б) - в исходном кодовом слове нечетное число единиц.


Для обнаружения ошибок в кодовом слове, состоящем из символов (в таблице ) производится две операции.

  1. Суммируются единицы, содержащиеся в первых k символах кодового слова.

2. Если число единиц четное, последующих символов сравниваются попарно с первыми k символами; если число единиц в первых символах нечетное, последующие символы перед сравниванием инвертируются.

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

Ошибка в кодовом слове не обнаруживается, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых символов. Например, если в. кодовом слове 1011001001 искажены 1-ый, 2-ой, 6-ой, 7-ой символы, то ошибка не может быть обнаружена, так как образуется другое разрешенное слово - 01110'10001.

В канале связи с независимыми ошибками вероятность необнаруженной ошибки при использовании инверсного кода (таблица 1.2) равна

(1.25)

то есть существенно меньше, чем в аналогичных условиях для 6-значного кода с проверкой на четность и 7-значного кода с постоянным весом.

Однако избыточность инверсного кода еще больше, чем 7-значного кода, и равна 0,5 (50%).



    1. Групповые коды


1.4.1 Кодирование и декодирование групповых кодов

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

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

В современной теории кодирования широко используются основные понятия высшей алгебры: множества, матрицы, векторные пространства, группы, кольца и поля [1,2,8,9]. Групповые коды образуют особый класс кодов, построение которых производится по определенным правилам, известным из теории множеств. Из класса групповых ходов в дальнейшем будут рассматриваться только двоичные коды.

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

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

Порядок группы равен , то есть равен числу кодовых слов в группе (числу элементов множества). Если для передачи информации используется k разрядов из общего числа , то количество кодовых слов в таком коде равно (подмножество группы порядка 2n). При этом подмножество группы называется подгруппой, если оно само по себе образует группу относительно операции сложения по модулю 2. В подгруппу обязательно входит нулевое слово, все кодовые символы которого равны нулю (нулевой член множества ). Например, группа , имеющая порядок содержит в себе всё подгруппы всех других порядков от до . Подгруппа состоит только из одного кодового слова вида 0000, а подгруппа есть сама группа , состоящая из 16 кодовых слов.

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

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

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

. (1.27)

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

Проверочная матрица строится для определения алгоритма кодирования и декодирования данного группового кода. Каноническая форма проверочной матрицы записывается путем дополнения k столбцов к единичной матрице r r (дополнение приписывается слева от единичной матрицы)

(1.28)

Рассмотрим пример.

Построить линейный код n = 7, обеспечивающий исправление одиночных ошибок.

Решение задачи:

Для исправления одиночной ошибки необходимо кодовое расстояние

d  2tи + 1 = 3.

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

2r  1+ C 17 = 8, то есть r  3. (1.29)

Строим производящую матрицу, для чего берём квадратную единичную матрицу из k = (n – r) строк и столбцов и путём перебора добавляем проверочные разряды так, чтобы расстояние между кодовыми словами было не меньше d. Четыре строки матрицы образуют 4 кодовых слова искомого кода.




1000 011

0100 110

0010 101

0001 111

1

2

3

4

12

1100 101

5

13

1010 110

6

14

1001 100

7

23

0110 011

8

24

0101 001

9

34

0011 010

10

123

1110 000

11

234

0111 100

12

134

1011 011

13

124

1101 010

14

1234

1111 111

15

(1.30)

Остальные 11 кодовых слов из общего числа 2k - 1 находятся суммированием по модулю 2 всевозможных сочетаний строк матрицы. Нулевое слово 0000 000 обычно не используется, хотя и принадлежит данному коду (принадлежит к выбранной подгруппе группы G7).

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

Таблица 1.3 Расстояния dij


i

j

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

4

0

4

4

0


dij

3

3

3

0


3

3

3

4

0

3

3

3

3

4

0

4

3

4

3

3

3

0

3

3

3

4

4

4

7

0

4

4

3

3

3

7

4

3

0

4

3

4

3

7

3

4

3

4

0

4

4

4

7

3

3

4

3

4

4

0

7

3

3

4

4

4

3

4

3

3

3

0


3

7

3

4

4

4

3

4

3

3

3

4

0

3

3

7

4

4

4

3

4

3

3

3

4

4

0

44

4

3

3

3

4

3

4

4

4

3

3

3

0


Как видно из таблицы, кодовое расстояние данного кода равно трём (d=3), то есть такой код способен исправить любые одиночные ошибки.

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

1 2 3 4 5 6 7



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

a2 a3 a4 a5 = 0,

a1 a2 a4 a6 = 0,

a1a3 a4 a7 = 0. (1.31)


Полученное уравнение определяет правило проверки всех комбинаций данного кода в процессе их декодирования в приёмнике. Операция кодирования в передатчике, т.е. вычисление проверочных кодовых элементов определяется алгоритмом

a5 = a2 a3 a4,

a6 = a1 a2 a4,

a7 = a1 a3 a4. (1.32)


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

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

a2 a3 a4 a5 = 1  0  0  0 = 1,

a1 a2 a4 a6 = 0  1  0  1 = 0,

a1 a3 a4 a7 = 0  0  0  1 = 1. (1.33)


Наличие единиц в процессе проверок указывает на искажение кодового слова, а результаты проверок являются элементами синдрома ошибки S(1,0,1).

Синдромом последовательности кодовых символов (синдромом ошибки) называется последовательность S, определяемая матричным равенством

S= zHT , (1.34 )

где HT  транспонированная проверочная матрица кода.

Учитывая, что z = a + e  декодируемая кодовая последовательность, e  последовательность ошибок, aHT = 0.

S= zHT =( a + e) HT = eHT. (1.35)

Если необходимо исправить ошибку, анализ элементов синдрома продолжается. На основании второй проверки делается заключение, что символы a1, a2, a4, a6 не искажены. Следовательно, искажённым является один из символов: a3, a5, a7 (код позволяет исправить только одиночную ошибку). Так как символ a3 входит и в первое, и во второе уравнения, то искажён именно он. Этот символ в принятом кодовом слове заменяется на противоположный. Получается кодовое слово 0110011, совпадающее с переданным.

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




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

Существенное упрощение процедуры декодирования достигается при использовании кодов Хэмминга и циклических кодов.


1.4.1 Коды Хэмминга

Кодами Хэмминга обычно называют групповые кода:

  • с кодовым расстоянием , исправляющие одиночные ошибки;

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

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

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

Кроме этого общего требования, для кодов Хэмминга является обязательным, чтобы результат проверок на четность при декодировании искаженного кодового слова указывал также номер разряда, в котором расположен искаженный символ. Этот номер представляется числом, которое образуется при записи результатов 1-ой, 2-ой, ...-ой проверок в двоичной системе счисления ().

Обозначим разряды кодового слова кода Хэмминга в виде последовательности , , ,...,..., где I, 2, 3,...k..., - натуральные числа, представляющие собой номера разрядов. Следовательно, первая проверка должна охватывать те нечётные символы, при записи номеров которых в двоичной системе счисления обязательно имеется единица в первом разряде двоичного числа, то есть , , , , и так далее;

.

Вторая и последующие проверки строятся следующим образом

,

,

. (1.36)


Проверочные символы располагаются в тех разрядах, которые участвуют только в одной проверке. Такими разрядами являются 1-ый 2, 4, 8, 16 и так далее .

Необходимое число проверочных разрядов в кодовом слове определяется выражением (1.29), которое для кодов Хэмминга () удобнее использовать в виде

Рассмотрим пример:

Необходимо закодировать кодом Хэмминга () комбинацию из пяти информационных символов 10011.

Определяем необходимое число проверочных разрядов: 25  2n/n откуда . Принимаем , .

Проверочные символыы должны занять I, 2, 4 и 8 разряды кода, а информационные 3(1), 5(0), 6(0), 7(1) и 9(1) разряды (в скобках указаны значения символов). Определяем значения проверочных символов согласно уравнениям (1.36):

,

,

,

.

Таким образом, передаваемое кодовое слово кода Хэмминга имеет вид 101100111.

Пусть в канале связи символ, находящийся в 5-ом разряде, был искажен и кодовое слово приняло вид 101110111. В приемнике в процессе декодирования производятся проверки согласно уравнениям (1.36):

,

,

,

.

Записываем результат проверки в виде , что равно десятичному числу 5, которое указывает номер искаженного разряда. Следовательно, в 5-ом разряде необходимо изменить 1 на 0.

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








Похожие:

Простейшие корректирующие коды iconДокументи
1. /Корректирующие коды в системах передачи информации/POC9_11.DOC
2. /Корректирующие...

Простейшие корректирующие коды iconКурсовая работа по дисциплине
Ос корректирующие коды используются в режиме обнаружения ошибок. Иногда в системах без ос допускается режим обнаружения ошибок. При...
Простейшие корректирующие коды iconПрограмма итогового междисциплинарного экзамена по специальности 230101 «Вычислительные машины, комплексы, системы и сети»
Помехоустойчивое кодирование (идея построения помехоустойчивых кодов, коды Хэмминга, циклические коды)
Простейшие корректирующие коды iconA и b a=1001,112 b=11,0112
...
Простейшие корректирующие коды iconКоды 2005 год (Новая классификация) Коды
Начисления на фонд оплаты труда (единый социальный налог), включая тарифы на обязательное социальное страхование от несчастных случаев...
Простейшие корректирующие коды iconКоды 2005 год (Новая классификация) Коды
Начисления на фонд оплаты труда (единый социальный налог), включая тарифы на обязательное социальное страхование от несчастных случаев...
Простейшие корректирующие коды iconДокументи
1. /monitoring/Коды льготных категорий граждан.doc
2. /monitoring/Коды...

Простейшие корректирующие коды iconДокументи
1. /monitoring/Коды льготных категорий граждан.doc
2. /monitoring/Коды...

Простейшие корректирующие коды iconКоды регионов Российской Федерации

Простейшие корректирующие коды iconЖож бойынша пән коды

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы