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




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

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

1. Построить кодеры для двоичных циклических кодов чины 15 с порождающими многочленами

а) Х4 + Х + 1; б) Х8 + Х7 + Х6 + Х4 + 1.

2. Всякий циклический (n, k)-код с порождающим многочленом g(х) можно представить в систематической форме следующим образом. Пусть ri(х) - остаток от деления xi на порождающий многочлен g(x), т. е.

xi = qi(x)g(x) + ri(x).

Рассмотрим многочлены

xi - ri(x) = qi(x)g(x)

при i = m, m+1, ..., n-1, где m = n-k - степень порождающего многочлена g(x). Все эти многочлены кодовые, так как они кратны g(x). Кодовый вектор, соответствующий многочлену xi - ri(x), имеет вид:

(-ri0, -ri1, ..., -ri, m-1, 0, ..., 1, ..., 0),

ri0, ri1, ri, m-1 - коэффициенты остатка ri(x), а символ 1 стоит в позиции с номером i.

Мы получили n - m = k векторов, которые, как нетрудно видеть, линейно независимы. Если составить матрицу G, строками которой являются указанные векторы, то она и будет порождающей (ее строки образуют базис кодового подпространства). Если через R обозначить матрицу, строками которой являются коэффициенты многочленов ri(x), то матрица G получается приписыванием к матрице - R справа единичной матрицы Еk порядка k и ее можно условно записать в виде:

G = -R | Ek. (4)

Отсюда легко следует (ср. § 11, задача 10), что в качестве проверочной можно взять матрицу

H = Em | RT.

По столбцам матрицы Н стоят коэффициенты остатков от деления многочленов x0, х1, ..., хn-1 на g(x).

3. Чтобы проиллюстрировать метод, изложенный в дополнении 2, рассмотрим снова (7,4)-код с порождающим многочленом 1 + x2 + x3. Имеем:

x3 = (x3 + x2 + 1) + x2 + 1,
x4 = (x3 + x2 + 1) + (x + 1) + x2 + x + 1,
x5 = (x3 + x2 + 1) + (x2 + x + 1) + x + 1,
x6 = (x3 + x2 + 1) + (x3 + x2 + x) + x2 + x.

Строками порождающей матрицы являются, следовательно, коэффициенты многочленов:


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


и


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

При кодировании с помощью матрицы (4) кодовое слово получается умножением информационного слова на эту матрицу (см. (6), § 11). В этом случае последние k символов аm, аm+1, ..., an-1 кодового слова совпадают с информационными символами, а все кодовое слово является линейной комбинацией строк порождающей матрицы (4) с коэффициентами аm, аm+1, ..., an-1. Учитывая, что по строкам матрицы R стоят коэффициенты остатков от деления многочленов хi на порождающий многочлен g(x), мы убеждаемся, что величины а0, а1, ..., am-1 являются коэффициентами остатка от деления многочлена

-(аmхm + аm+1хm+1 + ... + аn-1хn-1)

на многочлен g(x) (в случае двоичных многочленов знак минус перед скобкой можно опустить).

Следовательно, схемы деления могут быть использованы для нахождения проверочных символов кодовых слов циклического кода в систематической форме и, в конечном итоге, для построения его кодера. На рис. 23 приведена схема кодера двоичного (7, 4)-кода с порождающим многочленом 1 + х2 + х3, основанная на указанном принципе.

Рис. 23
Рис. 23

Проследим вкратце работу этой схемы в течение семи тактов. Первые четыре такта переключатели схемы находятся в положении А, следующие три - в положении В. В первые четыре такта информационные символы поступают (без изменений) на выход всей схемы и на выход схемы деления. В течение этих четырех тактов в последовательных ячейках схемы деления получаются коэффициенты остатка а0, а1, а2 от деления многочлена а6x6 + а5x5 + а4x4 + а3x3 на порождающий многочлен 1 + x2 + x3, т. е. проверочные символы (в схеме на рис. 18 на это ушло бы семь тактов, но в данной схеме три такта "экономятся", так как последовательность коэффициентов а6, а5, а4, а3 подается не на вход, а сразу на выход схемы деления). В последующие три такта проверочные символы - сначала а2, затем а1, затем а0 - поступают из схемы деления на выход всей схемы. Таким образом, по истечении семи тактов на выходе всей схемы получаем целиком кодовое слово.

Рекомендуем читателю проследить по тактам работу рассматриваемой схемы для случая а3 = 0, a4 = a5 = a6 = 1.

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




ИНТЕРЕСНО:

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

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

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

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

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

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

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

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

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

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

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