Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция 10. Циклические коды с d =2, обнаруживающие одиночную ошибку

Циклические коды с d =2, обнаруживающие одиночную ошибку

Такой код может быть получен с помощью образующего многочлена Р(Х) = х + 1 ® 11.

Пусть задана заданная для кодирования комбинация

G(X) = x3+x2+1 ® 1101.

Далее умножим G(X) на :

.

Эта операция в нашем случае (, т.е. nк =1) эквивалентна приписыванию к исходной кодовой комбинации нуля справа. Разделим произведение на Р(Х) и находим, что остаток R(X) = 1. Таким образом, кодовый многочлен циклического кода будет иметь вид

Итак, мы разместили единственный в нашем случае контрольный символ (он оказался равным 1) на приготовленное для него первой операцией место. nи nк

В закодированнном сообщении 11011, n = 5, nи =4, nк =1.

Полученное сообщение является одним из ансамбля N = 24 = 16 сообщений. Каждое из них нужно кодировать таким же образом. Чтобы избежать дополнительных 15 (или в общем случае ) расчетов прибегают к использованию образующей матрицы.

Образующая матрица

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

. (1)

Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р(Х). Для образующего многочлена Р(Х)=х+1 ® 11 все остатки равны единице и образующая матрица имеет вид

Четыре строки образующей матрицы представляют собой комбинации циклического кода. Нулевая комбинация состоит из нулей а0=00000. Последняя 16-я комбинация получается в результате суммирования по модулю 2 всех четырех строк образующей матрицы. Нетрудно видеть, что а15=11110. Остальные кодовые комбинации получаются путем суммирования по модулю 2 всех возможных сочетаний строк образующей матрицы.

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

Циклические коды с d =3

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

1. Определить число контрольных символов nк.

2. Выбрать образующий многочлен Р(Х).

3. Найти элементы дополнительной матрицы.

4. Составить образующую матрицу.

5. Найти все комбинации циклического кода.

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

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

а) степень образующего многочлена должна быть равна числу контрольных символов в кодовых комбинациях, определенному в п.1. Если, например, nк =3, то из таблицы образующих многочленов можно выбрать любой многочлен степени 3;

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

в) число не нулевых членов образующего многочлена Р(Х) не должно быть меньше кодового расстояния d.

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

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

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

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

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

Рассмотрим методику построения циклического кода, обнаруживающего двойные ошибки с d = 3.

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

Решение. Определяем число контрольных символов. Так как задано n и=4, то пользуемся формулой

n к = ]lb(n и+1)+]lb(n и+1)[[=]lb(5+3)[=3.

Из таблицы многочленов выбираем один из образующих многочленов третьей степени, причем такой, чтобы число не нулевых членов в нем было не меньше кодового расстояния (d =3), т.е. не меньше 3 P(X)=x3+x+1 ® 1011.

Находим остатки от деления единицы с соответствующим числом нулей на Р(Х):

 

0001000 1011

011 1-й остаток

 

0010000 1011

110 2-й остаток

 

0100000 1011

111 3-й остаток

 

1000000 1011

101 4-й остаток

Этих остатков должно быть четыре, так как n и=4.

Составляем образующую матрицу (a i -строки; Иj - информационные символы; Кl - контрольные символы):

Находим все остальные комбинации циклического кода:

5. a1Åa2=0011101

6. a1Åa3=0101100

7. a1Åa4=1001110

8. a2Åа3=0110001

9. a2Åa4=1010011

10. a3Åa4=1100010

11. a1Åa2Åa3=0111010

12. a1Åa2Åa4=1011000

13. a1Åa3Åa4=1100010

14. a2Åa3Åa4=1110100

15. a1Åa2Åa3Åa4=1111111

и 16-ю нулевую комбинацию - 0000000.

Тот же результат можно получить, если каждую из строк единичной транспонированной матрицы умножить на образующий многочлен. Образующий многочлен Р(Х)=х3+х+1 ® 1011. Первая строка транспонированной единичной матрицы 0001. В результате умножения получаем

´ 1011

0001

0001011.

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

´ 1011

0010

0010110.

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

000 1011

00 1011 0

0 1011 00

1011 000.

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

 

Циклический код с d=4

 

Этот код позволяет обнаруживать три ошибки.

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

1. Как и ранее, вначале определяется число контрольных символов n к, необходимое для обеспечения заданной помехоустойчивости. Начинают с нахождения числа контрольных символов для кода с d =3. При этом, по соответствующим формулам находят число контрольных символов n к для кода d =3. Число контрольных символов для кода с d =4 будет на единицу больше, т.е.

n к( d =4) = n к( d =3) +1. (*)

2. По таблице выбирается образующий многочлен, степень которого должна быть равна n к. Причем, выбирают наиболее короткий многочлен с числом ненулевых членов не менее кодового расстояния, т.е. в нашем случае не менее трех (n к( d =3)). Такой многочлен позволит создать циклический код, обнаруживающий две ошибки: d=r+s+1, причем r ³ s; r=2; s=0; d =3.

Образующий многочлен Р(Х) ( d =4) получается как произведение двучлена (х+1) на многочлен Р(Х) (d =3), т.е.

Р(Х) ( d =4) = Р(Х) ( d =3) (х+1). (**)

Для обнаружения трех ошибок степень образующего многочлена должна быть на единицу больше, т.е. не менее четырех. Многочлен третьей степени, при числе ненулевых членов равным трем, позволяет обнаруживать все двойные ошибки. Многочлен первой степени х+1 обеспечивает обнаружение нечетных ошибок. Таким образом, если составить образующий многочлен четвертой степени, необходимый для синтеза циклического кода при d =4, как произведение двучлена х+1 на многочлен Р(Х) ( d =3), то такой многочлен будет обладать корректирующими свойствами сомножителей, т.е. позволяет обнаруживать одну, две и три ошибки.

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

Пример. Пусть требуется закодировать циклическим кодом с d =4 сообщение

G(X)=x10 + x8 + x7 + x6 + x3 + x + 1 ® 10111001011.

Решение. Находим число контрольных символов. В нашей комбинации, подлежащей кодированию, одиннадцать информационных символов, т.е. n и=11. Тогда для d =3:

n к = ]lb(n и+1)+]lb(n и+1)[[=]lb(12+4)[=4.

Таким образом:

n к( d =3) = 4; n к( d =4) = n к( d =3) +1 = 4 + 1=5.

Выбираем образующий многочлен:

Для d =3.

Из таблицы многочленов выбираем многочлен четвертой степени

n к( d =3)=4 с число ненулевых членов, равным трем (d =3): P(X4)( d =3)=x4+x+1.

Для d =4.

Р(Х) ( d =4)=Р(Х) ( d =3)(х+1)=(х4+x+1)(х+1)=

542+1 ® 110101.

Выбираем одночлен .

Составим произведение :

Определяем значение пяти контрольных символов, которые должны занять место пяти нулей в конце полученного выше произведения. Для этого разделим полученное выражение на Р(Х) ( d =4) до получения остатка

 

1011100101100000 110101

110101 11111

110101

110101

111000

110101

110100

110101

Таким образом, остаток равен 00010, следовательно кодовая комбинация циклического кода

F(X)® 1011100101100010.

информ-е контр-е

символы

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

1011100101100010 110101

110101 11111

110101

110101

111000

110101

110101

110101

 

<== предыдущая лекция | следующая лекция ==>
Выставление счетов и методы расчета при поставке товаров | 
Поделиться с друзьями:


Дата добавления: 2014-12-16; Просмотров: 780; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.061 сек.