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




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

11. Линейные или групповые коды

Большинство рассмотренных выше кодов обладало следующим свойством: сумма (и разность) двух кодовых слов также являлась кодовым словом. Для кода с повторением это свойство очевидно. Ясно оно и для кода с общей проверкой на четность, потому что сумма двух слов с четным числом единиц есть также слово с четным числом единиц.

В § 9 был рассмотрен код Хемминга с системой проверочных соотношений (5). Обобщим теперь этот пример, выбрав в качестве кодового алфавита некоторое конечное поле F. Каждое слово x1x2 ... xn этого алфавита будем отождествлять с вектором (x1, x2, ..., xn) n-мерного пространства Ln (в котором координаты векторов являются элементами F). Вектор, соответствующий кодовому слову, будем называть кодовым. Систему проверочных соотношений запишем в виде системы уравнений:

b11x1 + b12x2 + ... + b1nxn = 0,
b21х1 + b22х2 + ... + b2nxn = 0,
. . . . . . . . . . . . . . . . . . (1)
bm1x1 + bm2x2 + ... + bmnxn = 0

с коэффициентами bij из F. Код, состоящий из всех слов х1х2 ... xn, для которых справедливы соотношения (1), называют кодом с проверками на четность.

Для такого кода выполняется следующее свойство: если векторы (a1, а2, ..., аn) и (b1, b2, ..., bn) являются кодовыми, а значит, решениями системы (1), то и их сумма (а1 + b1, а2 + b2, ..., аn + bn) также является решением этой системы и потому кодовым вектором. Справедливо и другое свойство решений системы (1): если, α - элемент поля F и (a1, а2, ..., аn) - решение системы (1), то и вектор (αa1, αа2, ..., αаn) также является решением системы (1). Оба отмеченных свойства проверяются непосредственной подстановкой в систему (1) векторов

1 + b1, а2 + b2, ..., аn + bn) и (αa1, αа2, ..., αаn).

Вместе эти свойства означают, что код с проверками на четность образует линейное подпространство в пространстве Ln всех n-буквениых слов. По этой причине коды с проверками на четность называют линейными кодами (двоичные линейные коды называют также групповыми). Если кодовое подпространство в пространстве Ln имеет размерность k, то употребляют для большей определенности термин линейный (n, k)-код.

Имеется очень много причин, по которым линейные коды являются важнейшими в теории кодирования. Одна из них связана с удобствами в обнаружении и исправлении ошибок, как это видно из примера, рассмотренного в § 9. Другая причина - это возможность компактного задания кода. Действительно, в случае линейного кода нет необходимости указывать полный список кодовых слов, ведь код вполне определен системой линейных уравнений (1) или матрицей этой системы (проверочной матрицей):


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

К числу других достоинств линейных кодов, которые связаны с предыдущими, относятся простые алгоритмы кодирования и декодирования, легко реализуемые электронными переключательными схемами. Вообще, можно сказать, что бурное развитие теории кодирования, которое происходило в последние десятилетия, объясняется главным образом тем, что к линейным кодам приложим хорошо развитый аппарат линейной алгебры и теории конечных полей.

Возвращаясь к рассмотренным ранее кодам, легко найдем их проверочные матрицы. Так, для кода с общей проверкой на четность имеем одно проверочное соотношение x1 + x2 + ... + xn = 0; соответственно этому проверочная матрица состоит из одной строки и имеет вид

H = (111 ... 1).

Из проверочных соотношений для кода с повторением

x1 - x2 = 0,
x1 - x3 = 0,
. . . . . . . .
x1 - xn = 0

получаем следующую проверочную матрицу:


Наконец, проверочная матрица двоичного кода Хемминга длины 7, как это следует из соотношений (5) § 9, выглядит так:


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

a1 = (a11, a12, ..., a1n),
a2 = (a21, a22, ..., a2n),
. . . . . . . . . . . . . . (3)
ak = (ak1, ak2, ..., akn)

- базисные векторы линейного кода. Тогда всевозможные кодовые векторы исчерпываются линейными комбинациями

α1а1 + α2а2 + ... + αkak, (4)

где коэффициенты αi - любые элементы исходного поля. Таким образом, система базисных векторов (3) полностью определяет линейный (n, k)-код. Матрица G, составленная из них,


называется порождающей матрицей кода.

Заметим, что базис можно выбрать не единственным образом, поэтому порождающая матрица G определена неоднозначно. Последнее, впрочем, верно и в отношении проверочной матрицы H.

Легко указать порождающую матрицу кода с повторением; она имеет вид:

G = (1 1 1 ... 1).

В качестве базисных векторов двоичного кода с общей проверкой на четность могут быть взяты, например, следующие n-1 векторов:

а1 = (1 1 0 0 ... 0),
а2 = (1 0 1 0 ... 0),
а3 = (1 0 0 1 ... 0),
. . . . . . . . . . . . . .
аn-1 = (1 0 0 0 ... 1).

Поэтому матрица


является порождающей матрицей этого кода.

При использовании линейного кода для передачи сообщений полезно знать и порождающую, и проверочную матрицу. С помощью порождающей матрицы удобно кодировать сообщения. Поскольку линейный (n, k)-код с порождающей матрицей (5) имеет qk кодовых слов (любой из k коэффициентов в (4) можно выбрать q способами), он позволяет закодировать все сообщения длины k в алфавите из q символов. Если А = α1α2 ..., αk - такое сообщение (αi - информационные символы), то самое удобное - сопоставить ему кодовый вектор я, совпадающий с линейной комбинацией (4) строк порождающей матрицы. Вектор а нетрудно записать в матричном виде, используя правило умножения матриц:


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


Этот код содержит 24 = 16 кодовых слов, которыми можно закодировать все двоичные сообщения длины 4. Если, например, А = (0101), то для соответствующего кодового вектора имеем:


О роли проверочной матрицы мы скажем в дальнейшем - она используется в основном при декодировании полученных сообщений и для исправления ошибок.

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

bi1аj1 + bi2аj2 + ... +binajn = 0. (7)

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

GHT = 0

(0 означает здесь нулевую матрицу).

Заметим также, что из соотношений (1) вытекает равенство

υHT = 0,

справедливое для каждого кодового вектора υ.

Для отыскания порождающей матрицы нужно фактически найти k = n - m линейно независимых решений системы (1). Эти решения как раз и будут строками порождающей матрицы.

Пример. Найдем порождающую матрицу кода Хемминга длины 7 с проверочной матрицей (2). В данном случае требуется найти 4 независимых решения следующей системы:

x4 + x5 + x6 + х7 = 0,
x2 + x3 + x6 + х7 = 0,
x1 + x3 + x5 + х7 = 0.

Разрешаем систему относительно неизвестных x1, х2, x4:

x1 = x3 + x5 + x7,
x2 = x3 + x6 + x7, (8)
x4 = x5 + x6 + x7,

Неизвестным x3, х5, x6, х7 можно придавать любые значения; тогда из равенств (8) могут быть определены оставшиеся неизвестные х1, x2, х4. Придавая поочередно одному из неизвестных x3, х5, x6, х7 значение 1, а остальным - 0, получим 4 решения:

а1 = (1110000),
а2 = (1001100),
а3 = (0101010),
а4 = (1101001),

которые, как читатель может убедиться, линейно независимы. Составленная из этих решений матрица


и является искомой порождающей матрицей.

По поводу сказанного в этом параграфе возникает множество вопросов. Например, как, зная порождающую и проверочную матрицы, выяснить корректирующие способности данного кода; как реализовать эти способности (т. е. каким должен быть алгоритм декодирования, исправляющий или обнаруживающий ошибки); как, наконец, после исправления ошибок выделить информационные символы?

Остановимся вначале на последнем вопросе. Пусть, исправив ошибки, мы получили некоторый кодовый вектор а = (а1, а2, ..., аn). Тогда соответствующие ему информационные символы α1, α2, ..., αk определяются из равенства (6). Иными словами, вектор (α1, α2, ..., αk) есть решение (как можно показать, - единственное) системы линейных уравнений:

a11α1 + a21α2 + ... + ak1αk = a1,
a12α1 + a22α2 + ... + ak2αk = a2,
. . . . . . . . . . . . . . . . . . . . . . .
a1nα1 + a2nα2 + ... + aknαk = an.

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

Линейный (n, k)-код называется систематическим, если его порождающая матрица имеет вид


или вид


т. е. если она получается приписыванием к единичной матрице порядка k некоторой матрицы из k строк и m = n - k столбцов (иначе говоря, матрицы порядка k × m).

В случае (9) равенство (6) принимает вид:


Таким образом, первые k символов любого кодового слова как раз и оказываются информационными, а остальные (они являются проверочными) связаны с информационными символами соотношениями:

ak+1 = p11α1 + p21α2 + ... + pk1αk,
ak+2 = p12α1 + p22α2 + ... + pk2αk,
. . . . . . . . . . . . . . . . . . . . (10)
an = p1mα1 + p2mα2 + ... + pkmαk,

Равенства (10), очевидно, образуют систему проверочных соотношений систематического линейного кода. Очень важно, что всякий линейный код в некотором смысле эквивалентен систематическому (см. дополнение 9).

Дальнейшее прольет свет и на другие вопросы, поставленные выше.

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




ИНТЕРЕСНО:

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

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

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

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

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

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

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

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

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

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

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