Реферат: Циклические коды. Коды БЧХ
Название: Циклические коды. Коды БЧХ Раздел: Рефераты по коммуникации и связи Тип: реферат | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ кафедра РЭС реферат на тему: «Циклические коды. Коды БЧХ» МИНСК, 2009 Циклические коды Циклическим кодом называется линейный блоковый (n,k)-код, который характеризуется свойством цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый многочлен g(x) степени r = n-k, являющийся сомножителем двучлена xn +1. Многочлен g(x) называется порождающим. Как следует из определения, в циклическом коде кодовые слова представляются в виде многочленов
Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным. Например, если код построен над полем GF(q)=GF(23 ), которое является расширением GF(2) по модулю неприводимого многочлена f(z)=z3 +z+1, а элементы этого поля имеют вид, представленный в таблице 1,
то коэффициенты Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=qm -1 на GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Как следует из определения общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена xn +1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x). Многочлен ошибок степени не более (n-1) определяется из выражения Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам. Пример.
Синдромный многочлен, используемый при декодировании циклического кода, определяется как остаток от деления принятого кодового слова на порождающий многочлен, т.е.
Следовательно, синдромный многочлен зависит непосредственно от многочлена ошибок е(х).Это положение используется при построении таблицы синдромов, применяемой в процессе декодирования. Эта таблица содержит список многочленов ошибок и список соответствующих синдромов, определяемых из выражения
В процессе декодирования по принятому кодовому слову вычисляется синдром, затем в таблице находится соответствующий многочлен е(х), суммирование которого с принятым кодовым словом дает исправленное кодовое слово, т.е. Примеры.
Допустим, что длина кода n=7, то результат приводим по mod x7 +1. При построении и декодировании циклических кодов в результате деления многочленов обычно необходимо иметь не частное, а остаток от деления. Пример. 1. 2. Матричное задание кодовЦиклический код может быть задан порождающей и проверочной матрицами. Для их построения достаточно знать порождающий g(x) и проверочный h(x) многочлены. Для несистематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, т.е. путем их умножения на x При построении матрицы H(n,k) старший коэффициент многочлена h(x) располагается справа. Пример.
Для циклического (7,4)-кода с порождающим многочленом g(x)=x3
+x+1 матрицы G(n,k)
и H(n,k)
имеют вид: Для систематического циклического кода матрица G(n,k)
определяется из выражения Пример.
Матрица G(n,k)
для (7,4)-кода на основе порождающего многочлена g(x)=x3
+x+1, строится в следующей последовательности Определяется R4,3
, используя Аналогичным способом определяется В результате получаем Используя выражение Проверочная матрица в систематическом виде строится на основе матрицы G(n,k)
, а именно: Пример.
Для (7,4)-кода матрица H(n,k)
будет иметь вид: Одна из основных задач, стоящих перед разработчиками устройств защиты от ошибок при передаче дискретных сообщений по каналам связи является выбор порождающего многочлена g(x) для построения циклического кода, обеспечивающего требуемое минимальное кодовое расстояние для гарантийного обнаружения и исправления t-кратных ошибок. Существуют специальные таблицы по выбору g(x) в зависимости от предъявляемых требований к корректирующим возможностям кода. Однако у каждого циклического кода имеются свои особенности формирования g(x). Поэтому при изучении конкретных циклических кодов будут рассматриваться соответствующие способы построения g(x). Коды БЧХ Одним из классов циклических кодов, способных исправлять многократные ошибки, являются коды БЧХ. Примитивным кодом БЧХ, исправляющим tu
ошибок, называется код длиной n=qm
-1 над GF(q), для которого элементы Здесь a - примитивный элемент GF(qm ). Порождающий многочлен определяется из выражения Число проверочных элементов кода БЧХ удовлетворяет соотношению Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, исправляющего двух кратные ошибки (tu =2). Исходя из определения кода БЧХ корнями многочлена g(x) являются: Порождающий многочлен определяется из выражения Примечание. Минимальный многочлен элемента b поля GF(qm
) определяется из выражения Значения минимальных многочленов будут следующими: Так как f1(x)= f2(x)= f4(x), то На практике при определении значений порождающего многочлена пользуются специальной таблицей минимальных многочленов (см. таблицу 8 приложения), и выражением для порождающего многочлена По заданной длине кода n и кратности исправляемых ошибок tu
определяют: - пользуясь таблицей минимальных многочленов, определяется выражение для g(x) в зависимости от m и j. Для этого из колонки, соответствующей параметру m, выбираются многочлены с порядками от 1 до j, которые в результате перемножения дают значение g(x). В выражении для g(x) содержаться минимальные многочлены только для нечетных степеней a, так как обычно соответствующие им минимальные многочлены четных степеней a имеют аналогичные выражения. Например, минимальные многочлены элементов Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, обеспечивающего tu =3. Определяем значения m и j. Из таблицы минимальных многочленов в соответствии с m=5 и j=5 получаем Заданные исходные данные: n и tu или k и tu для построения циклического кода часто приводят к выбору завышенного значения m и как следствие этого к неоправданному увеличению длины кода. Такое положение снижает эффективность полученного кода, так как часть информационных разрядов вообще не используется. Пример. Требуется построить циклический код, исправляющий двух кратные ошибки, если длина информационной части кода k=40. Согласно выражению для примитивного кода n=2m -1, ближайшая длина кода равна 63, для которой m=6, а r=mtu =12. Следовательно, код будет иметь n=63, k=51. Неиспользованных информационных разрядов будет 11(51-40). Подобное несоответствие в ряде случаев можно устранить, применяя непримитивный код БЧХ. Непримитивным кодом БЧХ, исправляющим tu
ошибок, называется код длины n над GF(q), для которого элементы Здесь bi -непримитивный элемент GF(qm ), а длина кода n равна порядку элемента bi . Примечание. Порядком элемента bi
является наименьшее n, для которого Пример.
Порядок элемента b3
поля GF(26
) равен 21, так как Порождающий многочлен непримитивного кода БЧХ, по аналогии с примитивным кодом, определяется из выражения Пример. Определить значение g(x) для построения непримитивного кода БЧХ над GF(2) длины n=20, исправляющего двух кратные ошибки. Из таблицы непримитивных элементов GF(2m ) (см. таблицу 7 приложения) выбираем поле, элемент b которого имеет порядок больший, но близкий к заданному n. Приложение Таблица 1 Разложение бинома хn +1 на неприводимые сомножители
Примечание. В разложение всех биномов входит сомножитель 03 с корнем 00. Все сомножители представлены в восьмеричной форме. Таблица 2 Элементы поля GF(16) как расширение GF(2) по примитивному многочлену a(z)=z4 +z+1
Таблица 3 Элементы поля GF(16) как расширение GF(4) по примитивному многочлену f(z)=z2 +z+2
Таблица 4 Элементы поля GF(4) как расширение GF(2) по примитивному многочлену f(z)=z2 +z+1
Таблица 6 Элементы поля GF(8) как расширение GF(2) по примитивному многочлену f(z)=z3 +z+1
Таблица 7 Непримитивные элементы поля GF(2m )
Таблица 8 Минимальные неприводимые многочлены в поле GF(2m )
Такими являются GF(26 ) и b3 , порядок которого n=21. Так как j=2tu
-1=2(2-1=3, то выражение для g(x) будет иметь вид Значения этих многочленов следующие: Выражения для f3 (x) и f9 (x) можно определить из таблицы минимальных многочленов, используя для этого параметр m выбранного поля GF(2m ) и порядковые номера сомножителей g(x). Для рассмотренного примера m=6, а порядковые номера равны 3 и 9. Поэтому ЛИТЕРАТУРА 1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с. 2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с. 3. Цапенко М.П. Измерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с. 4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с. 5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с. |