Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

Задачи и дополнения

1. В теории циклических кодов многочлены удобно трактовать не только как элементы кольца Fn, но и как элементы кольца многочленов F[X] с обычной операцией умножения многочленов. Условимся в последнем случае вместо обозначения а(х) пользоваться обозначением а(Х). Необходимость различать эти обозначения видна хотя бы из такого примера: если в кольце Fn имеет место хn - 1 = 0, то в кольце F[X] многочлен Хn - 1, разумеется, не является нулевым элементом.

Для циклических кодов существенно следующее свойство порождающего многочлена g(x):

Если в качестве g(x) выбран многочлен наименьшей степени, принадлежащий идеалу V, то многочлен g(X) ∈ F[X] является делителем многочлена Хn - 1.

Для доказательства разделим Хn - 1 на g(X) с остатком. Получаем:

Xn - 1 = h(X)g(X) + r(X), (10)

где степень r(Х) меньше степени g(X). В кольце Fn равенство (10) приобретает вид:

h(x)g(x) + r(x) = 0,

откуда заключаем, что r(х) должен принадлежать идеалу V, в то время как его степень меньше, чем степень g(x). Следовательно, r(х) = 0, но тогда и r(Х) = 0, т. е.

Xn - 1 = h(X)g(X). (11)

Многочлен h(Х), удовлетворяющий равенству (11), называется проверочным многочленом.

2. Воспользуемся определением проверочного многочлена для построения проверочной матрицы циклического кода.

Пусть h(x) = ∑kj=0 hjxj - проверочный многочлен кода. Из (11) следует, что если m - степень многочлена g(x), то h(x) имеет степень n-m, т. е. k = n - m. В силу (11) имеем также, что в кольце Fn проверочный и порождающий многочлены связаны равенством

h(x)g(x) = 0. (12)

Рассмотрим матрицу Н порядка m × n, имеющую следующий вид:


Первая строка этой матрицы составлена из коэффициентов многочлена h(х), записанных в обратном порядке (т. е. в порядке убывания степеней). Последующие строки составлены аналогичным образом из коэффициентов многочленов хh(х), ..., xm-1h(x).

Докажем, что матрица H является проверочной.

Действительно, пусть а(x) = ∑n-1i=0 aixi - произвольный кодовый многочлен. Рассмотрим идеал Vg(h(x)), порожденный проверочным многочленом h(х) и возьмем произвольный многочлен: b(х) = ∑n-1j=0 bjxj из этого идеала. Тогда a(x) = s(x)g(x), b(x) = q(x)h(x) и согласно (12)

a(x) b(x) = s(x) q(x) g(x) h(x) = 0.

С другой стороны, умножая многочлены а(х) и b(х) по правилам умножения в Fn (см. равенства (4)), получаем:

а(х) b(х) = (а0 + а1х + ... + an-1xn-1) (b0 + b1x + ... + bn-1xn-1) = (a0b0 + a1bn-1 + ... + an-1b1) + (a0b1 + a1b0 + ... + an-1b2)x + ... + (а0bn-1 + a1bn-2 + ... + an-1b0n-1.

Так как многочлен а(х)Ьb(х) нулевой, то и все его коэффициенты равны нулю, в частности

a0bn-1 + a1bn-2 + ... + аn-1b0 = 0.

Это равенство означает, что всякий кодовый вектор ортогонален вектору (bn-1, bn-2, ..., b0) который получается из произвольного многочлена b(x) ∈ V, если его коэффициенты записать в обратном порядке. Таким образом, в силу построения матрицы (13), каждая ее строка ортогональна любому кодовому вектору и, стало быть, эта матрица является проверочной.

3. Вернемся снова к примеру циклического (7,4)-кода с порождающим многочленом g(x) = 1 + x2 + x3. Как было доказано, многочлен g(X) = 1 + X2 + X3 является делителем многочлена X7-1. Легко проверить, что

Х7 - 1 = (Х - 1) (Х3 + Х +1) (Х3 + Х2 + 1).

Следовательно, для проверочного многочлена h(x) имеем:

h(x) = (x - 1) (х3 + х + 1) = 1 + x2 + x3 + x4 = (1011100).

Поэтому проверочной будет следующая матрица:


4. Исходя из равенств

9 - 1) = (Х - 1) (Х2 + Х + 1) (Х6 + Х3 + 1),
15 - 1) = (Х - 1) (Х2 + Х + 1) (Х4 + Х3 + Х2 + Х + 1) (Х4 + Х + 1) × (Х4 + Х3 + 1),

найти порождающие и проверочные матрицы всех двоичных циклических кодов длины 9 и длины 15.

5. Пусть f(X) = f0 + f1X + ... + fkXk - произвольный многочлен степени k. Многочлен f*(X) = Xkf(1/X) называют двойственным к f(Х).

Показать, что проверочная матрица циклического кода может быть записана в виде:


где h*(х) - многочлен, двойственный к проверочному многочлену h(x).

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

7. Пусть g*(х) - многочлен, двойственный к многочлену g(x). Показать, что

а) коды, порожденные многочленами g(x) и g*(x), эквивалентны;

б) если для кода с порождающим многочленом g(x) выполняется условие g(x) = g*(x), то кодовое подпространство такого кода вместе с каждым вектором υ = (а0, а1, ..., an-1) содержит также и вектор υ* = (аn-1, аn-2, ..., a0).

8. Среди циклических кодов особую практическую важность имеет один специальный класс кодов, предложенных американскими математиками Боузом, Чоудхури и Хоквингемом. Эти коды так и называются кодами БЧХ - по начальным буквам фамилий этих математиков. Теория кодов БЧХ выходит за рамки настоящей книги, и мы только объясним в нескольких словах, каким образом они определяются. Для этого нам потребуются некоторые дополнительные сведения из теории полей.

Будем говорить, что подмножество F является подполем поля F‾, если F есть поле относительно операций на F‾. Справедлива такая теорема:

Для любого конечного поля F можно указать конечное поле F‾, удовлетворяющее следующим условиям:

1) F есть подполе поля F‾;

2) F‾ содержит n корней уравнения Xn - 1 = 0;

3) не существует поля, обладающего свойствами 1 и 2 и имеющего меньше элементов, чем F‾.

Пусть теперь для поля F указано поле F‾ со свойствами 1) - 3). Пусть α - примитивный элемент поля F‾, а числа s и l таковы, что элемент αs имеет порядок n и s + l < q, где q - число элементов поля F<. Циклический код называется кодом БЧХ (с параметрами n, s, l), если он состоит из всех многочленов степени ≤ n-1 с коэффициентами из F, среди корней которых содержатся все элементы

αs, αs+1, αs+2, ... αs+l.

Можно доказать, что кодовое расстояние такого кода не меньше l + 2. Следовательно, варьируя параметры n, s, l, мы имеем возможность получать коды БЧХ с любым расстоянием, а значит, исправляющие любое заданное число ошибок. Это обстоятельство счастливо дополняется тем, что для указанных кодов разработаны удобные алгоритмы декодирования, основанные на вычислениях в конечных полях и легко реализуемые автоматическими электронными устройствами.

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

И вот здесь коды БЧХ обнаруживают некоторый изъян. Оказывается, при заданной корректирующей способности, т, е. заданной величине t/n, коды БЧХ большой длины имеют слишком высокую избыточность. Более того: если отношение t/n фиксировано, а n → ∞, то k/n → 0.

Стремление исправить этот недостаток привело к появлению таких кодовых конструкций, как коды-произведения (см. дополнение 12 к § 11) и их обобщение - каскадные коды. Строящиеся, как правило, на базе кодов БЧХ, они в значительной степени сохраняют их достоинства, но одновременно избавлены от упомянутого выше дефекта.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru