Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Тема 6. Построение кодов заданной помехоустойчивости. Применение недвоичных помехоустойчивых кодов.

Лекция



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

Тема 6. построение кодов заданной помехоустойчивости . применение недвоичных помехоустойчивых кодов .

Лекция 9.

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

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

Образование кодовых слов (кодирование) KC выполняется путем умножения информационного полинома (информационный полином – полином с коэффициентами, являющимися информационной последовательностью) Иi(X) порядка i<k на образующий полином:

КСm+i(Х) = gm(X) * Иi(X).

 

9.1 Матричное описание циклических кодов.

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

Вспомним, что KC(X) = gm(X)*И(Х).

Это соответствует описанному выше упрощенному способу умножения матриц:

<![if !vml]>Тема 6. Построение кодов заданной помехоустойчивости. Применение недвоичных помехоустойчивых кодов.<![endif]>

 

Образующая матрица ||OM|| это (k*n)- это матрица, при помощи которой происходит построение циклического кода. Образующая матрица получается в результате k- кратного циклического сдвига кодовой комбинации, соответствующей первой строке образующей матрицы.Первая строка образующей матрицы получается путем добавления слева от коэффициентов полинома gm(X) такого числа нулей, чтобы общая длина кодовой комбинации была равна n.

 

Например, образующий полином имеет видG(X)=111010001=X8+X7+X6+X4+1 при n=15 и k=7. Тогда первая строка образующей матрицы примет вид:000000111010001, а вся матрица:

0 0 0 0 0 0 1 1 1 0 1 0 0 0 1

0 0 0 0 0 1 1 1 0 1 0 0 0 1 0

0 0 0 0 1 1 1 0 1 0 0 0 1 0 0

0 0 0 1 1 1 0 1 0 0 0 1 0 0 0

0 0 1 1 1 0 1 0 0 0 1 0 0 0 0

0 1 1 1 0 1 0 0 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 1 0 0 0 0 0 0

 

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

 

9.2 Коды Боуза — Чоудхури — Хоквингема (БЧХ).

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

В БЧХ-коде образующий полинома представляет собой произведение нескольких неприводимых полиномов – мы далее посмотрим каких.

БЧХ коды, вообще-то говоря , как и линейные циклические коды в целом не обязательно являются двоичными., то есть с символами, из которых состоит код =1 или 0.

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

В БЧХ-кодах построение образующего полинома, в основном, зависит от двух параметров: от длины кодового слова n=k+r и от числа исправляемых ошибок S.

Особенностью кода является, то чтодля исправления числа ошибок S>=2 еще недостаточно условия, что между комбинациями кода минимальное кодовое расстояние dmin=2*S+1. Необходимо также, чтобы длина кода n удовлетворяла условию

 

n = 2h - 1,(1)

 

где h -любое целое число.

 

При этом длина кода n всегда будет нечетным числом и принимать значения: 1,3,7,15,31,63,127..и.т.д, т.е не все значения длины могут быть заданы пользователем.

 

Выбранная по формуле (1) величина n определяет число контрольных символов r.

 

r<=h*S<=log2(n+1)*S.(2)

 

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

 

Построение образующего полинома G(X) производится при помощи таблицы неприводимых полиномов M(X). Образующий полином представляет собой произведение неприводимых полиномов и является их наименьшим общим кратным (НОК). Максимальный номер неприводимого полинома в их произведении

 

p = 2*S - 1 .(3)

 

Порядок полинома используется при определении числа сомножителей. Для построения G(X) используются только нечетные полиномы.

Например, при S=4 ими будут: M1(X); M3(X); M5(X); M7(X). Старший из них имеет номер p=2*S-1=7. Число их равно 4, т.е. равно числу исправляемых ошибок.

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

 

V = S,(4)

 

а старшая степень

 

v= h(5)

 

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

 

b = r = v*S = h*S(6)

 

В общем виде G(X)=НОК[M1(X)M3(X)...Mp(X)].

 

Пример: Рассмотрим построение циклического кода длиной в 15 разрядов, исправляющего одну или две ошибки. Согласно (1) ,

 

n = 2h - 1, откуда h=log2(n+1) = log216 = 4

 

Число контрольных символов k, согласно (2),

 

r=log2(n+1)*S=4*2=8.

 

Номер старшего из неприводимых полиномов, согласно (3)

 

p = 2*S-1 = 2*2 -1 = 3.

 

Количество неприводимых полиномов, участвующих в построении образующего полинома, согласно (4),

 

V= S = 2,

 

старшая степень, согласно (5),

 

v = h = 4.

 

Степень образующего полинома , согласно (6),

 

b = r = 8.

 

Изтаблицы неприводимых полиномов выбираем полиномы степени v=4, из них выбираем два (V=2) неприводимых полинома , номер старшего из которых равен 3(p=3), т.е. Об этом говорит сайт https://intellect.icu . выбираем неприводимые полиномы p1 и p3 .

 

G(X)=M1(X)*M3(X) = 10011 * 11111 = 111010001 = X8+X7+X6+X4+1.

 

Число информационных разрядов

 

k = n - m = 15 - 8 = 7.

 

Первая строка образующей матрицы получается путем добавления слева от G(X) такого числа нулей, чтобы общая длина кодовой комбинации была равна n. Образующая матрица получается в результате m кратного циклического сдвига кодовой комбинации, соответствующей первой строке образующей матрицы.

 

0 0 0 0 0 0 1 1 1 0 1 0 0 0 1

0 0 0 0 0 1 1 1 0 1 0 0 0 1 0

0 0 0 0 1 1 1 0 1 0 0 0 1 0 0

||ОМ|| =0 0 0 1 1 1 0 1 0 0 0 1 0 0 0

0 0 1 1 1 0 1 0 0 0 1 0 0 0 0

0 1 1 1 0 1 0 0 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 1 0 0 0 0 0 0

 

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

 

9.3 Систематический вид циклического кода.

На практике иногда требуется закодировать в БЧХ- коде одну или несколько информационных посылок, для этого поступаем следующим образом:

 

1) выбираем образующий полином (методика выбора образующего полинома описана выше);

 

2) информационную комбинацию умножаем на одночлен той же степени, что и образующий полином;

 

3) делим полученную комбинацию на образующий полином;

 

4) суммируем остаток от деления с информационной комбинацией, умноженной на одночлен той же степени, что и образующий полином.

 

Например: информационную комбинацию вида 1001101 закодировать в БЧХ -коде, так чтобы код был способен исправлять ошибки кратности 2.

 

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

 

2. Умножаем 1001101 на Х8 (100000000), имеем 1001101*100000000=100110100000000

 

3.Делим 100110100000000 на 111010001, в результате деления по модулю два получаем остаток равный 11000010

 

4. Суммируем

100110100000000

+11000010

100110111000010-искомая комбинация.

 

Причем старшие 7 разрядов информационные, а оставшиеся 8 - контрольные.

 

 

 

Таблица9.1Разложение бинома хn+1 на неприводимые сомножители

Степень бинома

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

Неприводимые сомножители

7

1 2 4
3 6 5

13
15

15

01 02 04 08
03 06 12 09
05 10
07 14 13 11

023
037
007
031

31

01 02 04 08 16
03 06 12 24 17
05 10 20 09 18
07 14 28 25 19
11 22 13 26 21
15 30 29 27 23

045
075
067
057
073
051

63

01 02 04 08 16 32
03 06 12 24 48 33
05 10 20 40 17 34
07 14 28 56 49 35
09 18 36
11 22 44 25 50 37
13 26 52 41 19 38
15 30 60 57 51 39
21 42
23 46 29 58 53 43
27 54 45
31 62 61 59 55 47

103
127
147
111
015
155
133
165
007
163
013
141

 

9.4 Коды Рида–Соломонаи их применение.

Широко используемым подмножеством кодов БЧХ являются коды Рида-Соломона, которые позволяют исправлять пакеты ошибок. Пакет ошибок длины b представляет собой последовательность из таких b ошибочных символов, что первый и последний из них отличны от нуля. Существуют классы кодов Рида-Соломона, позволяющие исправлять многократные пакеты ошибок.

Коды Рида-Соломона (РС) в качестве двоичных элементов (1 или0) ) используют двоичные векторы V длиной 8 бит(байт) или иногда 4 бита (полубайт). Коды РС, таким образом, это не двоичные, а8ми- ричные коды БЧХ длины N=2m-1.

Они являются циклическими кодами с образующим полиномом

G(x)=M1(х)*M2(x)* …*Mi(X),

где полином G(X)перед степенями Xiимеет множитель в виде двоичного вектора длиной в 8 бит.

Выбор длины кода N=2m-1гарантирует, что полином G(X) является делителем XN-1 , и следовательно, всегда будет выполнено требование к образующему полиному циклического кода.

Слово кода Рида-Соломонаимеет вид:

A1A2… AkB1B2…BN-k,

где Ai и Bj– соответственно информационные и избыточные символы, которые могут быть представленыm-разрядными двоичными векторами. Число информационных символов – K=(N-ст.G(x)), гдест.G(x)степень образующего полинома G(x).

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

d=N-K+1.

Коды РС являются линейными кодами, поэтому, кроме задания с помощью образующего полинома G(X), они могут быть заданы также образующей||ОМ|| матрицей.

 

Пример8-ричного (7,3) кода Рида - Соломона

Образующий полином вполе Галуа GF(23)

g(x) =x4+ α6x3+ α6x2+ α3x+ α,

где α -первообразный элемент поля Галуа GF(23). Это восьмеричное или 3-х значное двоичное число, такое, что αi пробегают все значения элементов поля GF(23).

Пусть исходное кодовое слово, состоящее из восьмеричных чисел имеет вид

ИС = α4 , α0 3.

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

m(x) = α4x2+x+ α3

Кодовое словокода Рида-Соломоназапишется в виде

c(x) =m(x)g(x) = (α4x2+x+ α3)(x4+ α6x3+ α6x2+ α3x+ α) = α4x6+ αx5+ α6x4+ 0x3+ 0x2+ α5x+ α4 =(α4, α,α6, 0, 0, α5,α4 )

что представляет собой последовательность семи восьмеричных символов

 

Применение кодов Рида–Соломона

Сразу после появления (60-ые годы 20ого века) коды Рида - Соломона стали применяться в качестве внешних кодовспутниковой связи. В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.

Запись и хранение информации

Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на магнитные жесткие диски . Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации.

Коды Рида-Соломона широко используются в устройствах цифровой записи звука, в том числе на компакт-диски. Данные, состоящие из отсчетов объединяются в кадр, представляющий кодовое слово. Кадры разбиваются на блоки по 8 бит. Часть блоков являются контрольными.

Обычно 1 кадр (кодовое слово) = 32 блока *8(биты данных +сигнальные биты + контрольных биты)= 256 бит.

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

При передаче данных производится перемежение (изменение порядка следования по длине носителя и во времени) блоков с различным сдвигом во времени, в результате чего расчленяются сдвоенные ошибки, что облегчает их локализацию и коррекцию. При этом используются коды Рида-Соломона с неприводимым кодовым расстояниемd0= 5. Это означает, что они способны исправить две байтовые ошибки в каждом кодовом слове кадра в 256 бит.

 

9.5 Циклический избыточный кодCRC.

 

Циклический избыточный кодCRC( Cyclic Redundancy Check — циклическая избыточная проверка) являютсясистематическимикодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деленияxru(x)наg(x). Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полиномаg(x)задает конкретный код CRC. Эти полиномы стандартизированы и имеют следующий вид. :

 

название кода

степень

полином

CRC-12

12

x12+x11+x3+x2+x+ 1

CRC-16

16

x16+x15+x2+ 1

CRC-CCITT

16

x16+x12+x5+ 1

CRC-32

32

x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+ 1

Таблица 9.2

 

9.6 Контрольные вопросы.

1. Каким образом строится полином для получения циклического кодазаданной помехоустойчивости?

2. Перечислите основные этапы построения кодов БЧХ.

3. Упрощенный метод кодирования при кодировании одного кодового слова.

4. В чем особенность построения и применения кодов Рида-Соломона,

исправляющих пакеты ошибок?

5. Можно ли выбирать произвольный образующий полином в CRC кодах?


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

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

создано: 2015-01-24
обновлено: 2021-03-13
132577



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Теория информации и кодирования

Термины: Теория информации и кодирования