Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет Ф. И. Соловьева ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ Учебное пособие Рекомендовано учебно-методическим Советом по математике и механике УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности “010100 Математика” Новосибирск 2006 2 УДК 519.725(075) ББК з-811.4 я 73-1 С603 Соловьева Ф. И. Введение в теорию кодирования: Учебное пособие / Новосиб. гос. ун-т. Новосибирск, 2006. с. 127. В настоящем учебном пособии изложены математические основы современной теории кодов, исправляющих ошибки в каналах связи с шумами. Пособие отражает содержание основной части лекций, читаемых автором в данное время в качестве основных курсов лекций по теории кодирования на механико-математическом фа- культете и факультете информационных технологий, а также читаемых в течение ряда лет в качестве специального годового курса "Введение в теорию кодирования" на механико-математическом факультете. Предназначено для студентов названных выше факультетов, а также может быть полезно студентам физического факультета, интересующимся математическими основами проблем передачи данных по каналам связи с помехами. Рецензенты проф., д-р техн. наук В. В. Зяблов, ИППИ РАН д-р физ.-мат. наук С. А. Малюгин, ИМ СО РАН c ° Новосибирский государственный университет, 2006 c ° Ф. И. Соловьева Введение Коды возникли в глубокой древности фактически с появлением системы знаков для записи звуков, слов, информации, которые позднее развились в различные язы- ки. Каждый язык представляет собой сложную систему кодирования, включая в свою конструкцию алфавит, слова, грамматику. Язык позволяет в окружающем шу- ме передавать информацию по возможности быстро, надежно, с достаточно высокой степенью избыточности. Позднее появились (еще до нашей эры) криптограммы (по-гречески криптограм- ма – тайнопись). Такими кодами пользовались для засекречивания сообщений. Уже в V в. до н. э. знаменитый греческий историк Геродот приводил примеры писем- криптограмм, понятных только одному адресату. Спартанцы имели специальный ме- ханический прибор, при помощи которого записывались сообщения–криптограммы, позволяющие сохранить тайну. Собственную секретную азбуку имел Юлий Цезарь (широко известный шифр Цезаря). В Средние века и эпоху Возрождения над изоб- ретением тайных шифров работали многие выдающиеся умы, в том числе философ Фрэнсис Бэкон, математики Франсуа Виет, Джероламо Кардано. Криптографией за- нимались в монастырях, при дворах королей. Вместе с искусством шифрования сооб- щений развивалось и искусство их дешифрования. Многие оптимистично полагали, что вряд ли существует такая криптограмма, которую нельзя разгадать. И только в прошлом веке Клод Шеннон (1949 г.) показал, что существует совершенно секрет- ный шифр – шифр Вернама, называемый также лентой однократного действия или шифром-блокнотом. В настоящее время теория кодирования имеет важное широкое практическое при- менение как средство экономной, удобной, быстрой, а также надежной передачи со- общений по линиям связи с различного вида шумами (телефон, телеграф, радио, телевидение, компьютерная, космическая связи и т. д.). Подлинный взрыв развития теории связи начался в послевоенные годы, с 1948–1949 гг., с появлением классиче- ских работ Клода Шеннона и Норберта Винера. Труды Н. Винера были порожде- ны исследованиями военного времени по автоматическому управлению огнем, труды К. Шеннона знаменитые "Математическая теория связи" и "Связь при наличии шума" – исследованиями по шифрованию сообщений и их передачи по секретным каналам связи. Математические модели Н. Винера и К. Шеннона довольно сильно различались: сигнал по Н. Винеру может обрабатываться после воздействия шумом, по К. Шеннону сигнал можно обрабатывать как до, так и после передачи по каналу связи с шумами. В силу этого и других различий, Винеровские труды легли в основу теории автоматического управления, Шенноновские труды оказались основопола- гающими для задач эффективного использования каналов связи. Таким образом, с 1949 г., с фундаментальных работ К. Шеннона, началось бурное развитие теории 3 4 кодирования как отдельной научной дисциплины, а также развитие таких тесно с нею связанных научных дисциплин, как сжатие информации и криптология. В настоящем курсе лекций рассматриваются блоковые коды, предназначенные для исправления случайных ошибок в каналах связи с шумами, в основном будет изучаться модель двоичного симметричного канала связи, хотя многие результаты без труда могут быть обобщены для кодов над q-значными алфавитами. Мы толь- ко коснемся определений некоторых других типов ошибок. В курсе лекций будет изложена теория линейных кодов, в частности теория q-значных циклических ко- дов, имеющих широкое применение на практике для передачи сообщений в каналах связи с шумами, доказана известная теорема Шеннона о существовании хороших кодов в двоичных симметричных каналах связи с шумами, предложены различные методы построения кодов (среди них – свитчинговые и каскадные методы), а также рассмотрены известные классы кодов, таких как коды Рида – Маллера, Адамара, совершенные коды, коды Рида – Соломона, коды Юстесена, Препараты. При подго- товке пособия были использованы источники [1–25]. 5 Основные понятия и определения Пусть E n обозначает n-мерное метрическое пространство всех двоичных векторов длины n с метрикой Хэмминга (см. ниже примеры двумерных проекций E n при малых n на рис. 1 и общепринятую модель E n для произвольного n на рис. 2). Произвольное подмножество C пространства E n называется двоичным кодом длины n, элементы кода называются кодовыми словами. 3 4 000 100 010 001 011 101 110 111 0111 0011 1111 1011 0101 0001 1101 1001 0110 0010 1110 1010 0100 0000 1100 1000 E E Рис. 1. Двумерные проекции E 3 и E 4 Хэммингово расстояние d(x, y) между векторами x, y ∈ E n определяется как число координат, в которых эти векторы различаются. Нетрудно показать, что оно является метрикой. Кодовое расстояние равно минимальному расстоянию Хэмминга между различными кодовыми словами. Вес Хэмминга w(x) произвольного вектора x ∈ E n равен числу ненулевых коор- динат x, т. е. w(x) = d(x, 0 n ), где 0 n – нулевой вектор длины n. Обозначим через 1 n единичный вектор длины n (иногда далее длины нулевого и единичного векто- ров указываться не будут, но из контекста всякий раз будет ясно, какова их длина). Множество supp(x) = {i | x i = 1} называется носителем вектора x. Известно, что группа автоморфизмов Aut(E n ) пространства E n исчерпывается подстановками π на множестве координат и добавлением произвольного вектора v ∈ E n , т. е. для группы автоморфизмов Aut(E n ) пространства E n справедливо Aut(E n ) = E n h S n = {(v, π) | v + π(E n ) = (E n ), v ∈ E n , π ∈ S n }, где h – полупрямое произведение, S n – симметрическая группа подстановок длины n. 6 E n E Í 0 n 1 – E Í 1 n 1 – i-é ñëîé Рис. 2. Двумерная проекция E n Два кода – C и D – длины n называются эквивалентными, если существует автомор- физм (v, π) пространства E n , отображающий один код в другой, т. е. v + π(C) = D. Группа автоморфизмов Aut(C) произвольного кода C длины n состоит из всех автоморфизмов пространства E n , переводящих код в себя, т. е. Aut(C) = {(v, π) | v + π(C) = C}. Множество Sym(C) = {π ∈ S n | π(C) = C} называется группой симметрий кода C. Очевидно, что Sym(C) изоморфна подгруппе группы Aut(C). Линейным (или групповым) кодом называется подмножество E n , являющееся ли- нейным подпространством (подгруппой) в E n . Аналогично, линейным q–значным ко- дом называется линейное подпространство n–мерного метрического пространства E n q всех векторов длины n с метрикой Хэмминга над полем Галуа GF (q), q = p k , q ≥ 2, где p–простое число (такой код может не являться групповым в E n q ). В дальнейшем параметры линейного кода C длины n с кодовым расстоянием d будем обозначать через [n, k, d], где k – размерность кода; для нелинейного кода C параметры будем обозначать через (n, |C|, d). Линейный код длины n называется циклическим, если для любого кодового слова (x 1 , x 2 , . . . , x n ) слово (x 2 , . . . , x n , x 1 ) также является кодовым. Для полноты изложения в дальнейшем некоторые из приведенных определений будут повторены. Упражнение 1. Доказать, что расстояние Хэмминга является метрикой, а E n — метрическим пространством: а) d(x, y) ≥ 0, причем d(x, y) = 0 ⇔ x = y (аксиома тождества); б) d(x, y) = d(y, x) (аксиома симметрии); в) d(x, y) + d(y, z) ≥ d(x, z) (аксиома треугольника) для ∀x, y, z ∈ E n Упражнение 2. Найти число вершин и ребер в E n , E n q 7 Упражнение 3. Найти число вершин: а) в сфере радиуса r в E n , E n q ; б) в шаре радиуса r в E n , E n q Двоичный симметричный канал связи Пусть по каналу связи с шумом пересылаются двоичные сообщения из Новосибир- ска в Москву. Рассмотрим случай, когда входной алфавит A совпадает с выходным алфавитом B и равен {0, 1}. Пусть при посылке 0 принимается как 0, а 1 как 1, но иногда 0 может быть принят как 1 или 1 принята как 0. Пусть в среднем один из каждых 1 000 символов будет ошибочным. Это означает, что для каждого символа имеется вероятность p = 1/1 000 того, что в канале связи произойдет ошибка, т. е. для переходных (условных) вероятностей P (β|α), где P α∈A P (β|α) = 1, имеем P (0|0) = P (1|1) = p и P (1|0) = P (0|1) = 1 − p. В данном случае переходные вероятности образуют симметричную матрицу и посе- му такая модель называется двоичным симметричным каналом связи. Сообщения должны передаваться как можно быстрее, экономнее и надежнее. Будем записывать сообщения в виде последовательностей из нулей и единиц. Закодируем эти сообще- ния в целях защиты их от ошибок, которые могут произойти в канале связи. Входная информация разбивается на блоки длины k. Каждый блок из k символов сообщения u = (u 1 , u 2 , . . . , u k ), u i ∈ {0, 1} преобразуется кодером в слово x длины n : x = (x 1 , x 2 , . . . , x n ), x j ∈ {0, 1}, n > k. Полученные слова образуют двоичный код и называются кодовыми словами. Схема- тично это представлено на рис. 3. Источник сообще- ний - Кодер - Канал связи - Декодер - Получа- тель Шум 6 Рис. 3. Классическая схема системы связи по каналу связи с шумом Так как канал с шумом, то принятый вектор y может отличаться от кодового слова x на вектор e, называемый вектором ошибок y = x + e, e = (e 1 , e 2 , . . . , e n ), где с вероятностью (1 − p) имеем e i = 0 (в этом случае i-й символ правильный) и с 8 вероятностью p имеем e i = 1 (i-й символ исказился). В общем случае вероятность p может быть произвольным числом, удовлетворяющим неравенству 0 < p < 1/2. Опишем некоторые другие, отличные от симметричных типы ошибок. Если для переходных вероятностей имеются запреты, то канал связи получается с односторон- ними ошибками, если в алфавит (входной и (или) выходной) включен пустой сим- вол, то получаем канал связи со вставками или выпадениями. Рассмотрим подробнее несколько случаев. 1. Несимметричная ошибка типа {1 → 0} (ее называют также замещением вида 1 → 0) может возникнуть в ситуации, когда происходит замена 1 на 0, но не на- оборот. Если наличию физического сигнала соответствует 1, а отсутствию – 0, то такие ошибки происходят в результате размыканий (обрывов) в канале, так как при размыкании сигнал может лишь исчезнуть. 2. Несимметричная ошибка типа {0 → 1} (замещение вида 0 → 1) аналогична предыдущей и происходит в результате замыканий в канале. 3. Ошибка стирания {0 → z, 1 → z} возникает в случае, если сигнал, представ- ляющий собой 0 или 1, искажается в канале так, что его нельзя интерпретировать ни как 0, ни как 1. Этот символ заменяется неопределенным символом, который обозначается через z. 4. Ошибка вида 0 → ∧ (1 → ∧) состоит в удалении одного из символов кодово- го слова x, в результате чего длина слова уменьшается на единицу. Такие ошибки называют выпадениями символов (в выходной алфавит включен пустой символ). 5. Ошибка вида ∧ → 0 (∧ → 1) состоит во вставке символа 0 (1) перед некоторым символом или после последнего символа слова x, в итоге длина кодового слова уве- личится на единицу. Одиночные ошибки такого типа называют вставками символов. Существуют также другие виды ошибок. Глава 1 Линейные коды 1.1. Линейные коды Напомним, что линейным (или групповым) двоичным кодом называется подмно- жество E n , являющееся линейным подпространством (подгруппой) в E n . Произволь- ный линейный код с параметрами [n, k, d] можно задать различными способами: аналитически, с помощью одной формулы (такой способ задания линейного кода не всегда может найтись); посредством кодовой матрицы порядка 2 k × n (строками матрицы являются ко- довые слова); порождающей матрицы порядка k × n (в строки записаны кодовые слова, обра- зующие базу линейного кода); проверочной матрицы – матрицы H такой, что для любого кодового слова x = (x 1 , x 2 , . . . , x n ) выполняется H x 1 x 2 x n = Hx T = 0 n−k , здесь H – матрица порядка (n − k) × n. Последнее уравнение задает (n − k) провероч- ных уравнений. Очевидно, что такое представление линейного кода также является аналитическим. Следует отметить, что для данного линейного кода представление порождающей (проверочной) матрицей не единственно. Опишем подробнее задание линейного кода посредством проверочной матрицы, имеющей канонический вид. Пусть от отправителя в кодер поступило сообщение u = (u 1 , u 2 , . . . , u k ). Сформируем кодовое слово x = (x 1 , x 2 , . . . , x n ). Положим первую часть кодового слова состоящей из символов самого сообщения (называемых инфор- мационными символами): x 1 = u 1 , x 2 = u 2 , . . . , x k = u k . Далее следуют n − k символов, называемых проверочными x k+1 , . . . , x n . Они выбираются таким образом, чтобы все кодовые слова удовлетворяли уравнению Hx T = 0 n−k . 9 10 Глава 1. Линейные коды Пусть матрица H имеет вид [A n−k,k |E n−k ], называемый каноническим, где A n−k,k – некоторая матрица порядка (n − k) × k из 0 и 1, E n−k – единичная матрица порядка n − k. Все операции выполняются над полем Галуа GF (2) характеристики 2. Теорема 1. О связи проверочной и порождающей матриц. Если прове- рочная матрица линейного кода задана в каноническом виде H = [A n−k,k |E n−k ], то порождающая матрица этого кода имеет вид G = [E k | − A T n−k,k ]. Верно обратное. Доказательство. Рассмотрим произвольное кодовое слово x = (x 1 , . . . , x k , x k+1 , . . . , x n ), где x k+1 , . . . , x n – проверочные символы, а x 1 , . . . , x k – информационные, т. е. инфор- мационный блок имеет вид u = (u 1 , . . . , u k ), где x 1 = u 1 , x 2 = u 2 , . . . , x k = u k , что можно записать в матричном виде x 1 x k = E k u 1 u k . (1.1) Пусть A = a 11 a 12 . . . a 1k a 21 a 22 . . . a 2k . . . . . . . . . . . . a n−k a n−k,2 . . . a n−k,k . Тогда из определения проверочной матрицы имеем Hx T = 0, т. е. a i1 x 1 + a i2 x 2 + . . . + a ik x k + x k+i = 0 для любого i = 1, . . . , n − k. Отсюда x k+i = −(a i1 x 1 + a i2 x 2 + . . . + a ik x k ), i = 1, . . . , n − k. Таким образом, x k+1 x n = −A n−k,k x 1 x k = −A n−k,k u 1 u k . Из последнего и из уравнения (1.1.) имеем x T = µ E k −A n−k,k ¶ u T . Транспонируя, получаем: x = u G, где G = [E k | − A T n−k,k ]. N Заметим, что теорема верна для q-значных кодов. 1.2. Границы объемов кодов 11 Упражнение 4. Найти число различных базисов в E n Упражнение 5. Найти число различных линейных двоичных кодов длины n размерности k. Упражнение 6. Показать, что в двоичном линейном коде либо каждый кодо- вый вектор имеет четный вес, либо половина кодовых векторов имеет четные веса и половина — нечетные. Упражнение 7. Доказать, что ненулевой столбец кодовой матрицы линей- ного [n, k]-кода содержит ровно 2 k−1 единиц. Упражнение 8. Доказать, что для любого линейного кода справедливо HG T = 0 для любых проверочной и порождающей матриц H и G этого кода со- ответственно. 1.2. Границы объемов кодов Рассмотрим несколько известных границ мощностей кодов. Теорема 2. Граница Хэмминга. Для любого двоичного кода C длины n (не обя- зательно линейного) с кодовым расстоянием d выполняется неравенство |C| ≤ 2 n P [(d−1)/2] i=0 C i n . Доказательство. Обозначим t = [(d−1)/2]. Поскольку кодовое расстояние равно d, то шары S n t (x) = {y | y ∈ E n , d(y, x) ≤ t]} радиуса t, описанные около кодовых слов x, не пересекаются. Очевидно, что все они имеют одинаковый объем, равный |S n t (0 n )| = C 0 n + C 1 n + . . . + C [ d−1 2 ] n . Следовательно, |C| × |S n t (0 n )| ≤ 2 n . (1.2) Подставляя |S n t (0 n )| в неравенство (1.2.), получаем требуемое. N Определение. Код называется совершенным или плотно упакованным, если |C| = 2 n P [(d−1)/2] i=0 C i n , т. е. имеет место плотная упаковка E n шарами радиуса [(d − 1)/2]. Справедливы следующие утверждения. Утверждение 1. Кодовое расстояние [n, k, d]-линейного кода равно минималь- ному из весов его ненулевых кодовых слов. 12 Глава 1. Линейные коды Теорема 3. О столбцах проверочной матрицы. Если H – проверочная мат- рица кода длины n, то код имеет кодовое расстояние d тогда и только тогда, когда любые d − 1 столбцов матрицы H линейно независимы и найдутся d линейно зави- симых столбцов. Доказательство. Необходимость. Вектор x веса ω принадлежит коду тогда и только тогда, когда Hx T = 0, (1.3) что эквивалентно линейной зависимости некоторых ω столбцов матрицы H. Обозна- чим i-й столбец матрицы H через h i , т. е. H = [h 1 , h 2 , . . . , h n ]. Отсюда и из равенства (1.3) получаем n X i=1 h i x i = 0, откуда следует соотношение линейной зависимости h i 1 + . . . + h i w = 0. По утвержде- нию 1 кодовое расстояние кода равно минимальному из весов его ненулевых кодовых слов. По условию теоремы код имеет кодовое расстояние d, откуда получаем линей- ную зависимость некоторой совокупности d столбцов матрицы H. Если существует d − 1 линейно зависимых столбцов в матрице H, то найдется вектор веса d − 1, принадлежащий коду C, противоречие. Достаточность очевидна. N Непосредственным следствием теоремы 3 является следующая верхняя граница объема кода. Теорема 4. Граница Синглтона. Для любого линейного [n, k, d]-кода выпол- няется n − k ≥ d − 1. Код, достигающий границу Синглтона, называется MDS-кодом. Код, полученный из данного кода удалением одной или более координат во всех кодовых словах, на- зывается выколотым кодом. Теорема 5. Граница Синглтона для нелинейных q-значных кодов. Для любого (n, M, d) q -кода выполняется log q M ≤ n − d + 1. Доказательство. Удаляя в (n, M, d) q -коде последовательно любые d − 1 коор- динат, получим код длины n − d + 1 с кодовым расстоянием по крайней мере 1 и мощности M. N Теорема 6. Граница Плоткина. При n < 2d для любого двоичного (n, M, d)-кода C справедливо неравенство M ≤ 2[d/(2d − n)], где M – мощность кода C. 1.2. Границы объемов кодов 13 Доказательство. Вычислим двумя способами сумму S = X u∈C X v∈C,v6=u d(u, v) для различных кодовых слов u и v из C. Поскольку при u 6= v расстояние d(u, v) ≥ d, то сумма не меньше, чем M(M − 1)d. С другой стороны, пусть A обозначает кодовую (M × n)-матрицу, строками которой являются все кодовые слова. Предположим, что i-й столбец матрицы A содержит x i нулей и M −x i единиц. Тогда вклад этого столбца в сумму S равен 2x i (M − x i ). Суммируя по всем столбцам, получаем S = n X i=1 2x i (M − x i ). При четном M максимум этого выражения достигается при x i = M/2 для любого i, следовательно, эта сумма не превышает nM 2 /2, т. е. имеем M(M − 1) d ≤ nM 2 /2, отсюда M ≤ 2d/(2d − n). Так как M четно, то M ≤ 2[d/(2d − n)]. При нечетном M эта сумма не превышает n(M 2 − 1)/2 и, следовательно, M ≤ n/(2d − n) = 2d/(2d − n) − 1. Отсюда с учетом [2x] ≤ 2[x] + 1 получаем M ≤ [2d/(2d − n)] − 1 ≤ 2[d/(2d − n)]. N Теорема 7. Граница Варшамова–Гилберта. Если выполняется неравенство 1 + C 1 n−1 + · · · + C d−2 n−1 < 2 r , то существует двоичный линейный код длины n с минимальным расстоянием по крайней мере d, имеющий не более чем r проверочных символов, т. е. [n, k, d 0 ]–код, где k ≥ n − r, d 0 ≥ d. Доказательство. Теорема будет доказана, если построим (r × n)-матрицу H такую, что любые ее d − 1 столбцов линейно независимы. Тогда, применяя теорему 3, получаем требуемое утверждение. В качестве первого столбца матрицы H возьмем любой ненулевой вектор длины r. Предположим, что выбрали i столбцов матрицы H так, что любые d − 1 из них линейно независимы. Имеем не более C 1 i + . . . + C d−2 i 14 Глава 1. Линейные коды различных ненулевых линейных комбинаций из этих i столбцов, содержащих d − 2 или меньше столбцов. Если это число меньше, чем 2 r − 1 (числа всех ненулевых векторов длины r), то мы можем добавить еще один столбец, не равный ни одной из всех этих линейных комбинаций. При этом любые d − 1 столбцов новой матрицы размера r × (i + 1) по-прежнему остаются линейно независимы. Будем выполнять эту процедуру до тех пор, пока выполняется неравенство C 1 i + . . . + C d−2 i < 2 r − 1. N Упражнение 9. Обобщить для q-значных кодов границы: а) Хэмминга; б) Варшамова–Гилберта. Упражнение 10. Доказать утверждение 1 и теорему 4. 1.3. Код Хэмминга и его свойства 1.3.1. Определение кода Хэмминга Для построения линейного кода Хэмминга с m проверками на четность, исправ- ляющего одну ошибку, воспользуемся теоремой 3: определим код посредством про- верочной матрицы, столбцами которой являются все ненулевые векторы длины m. Очевидно, что любые два столбца этой матрицы линейно независимы и найдутся три линейно зависимых столбца, следовательно по теореме 3 кодовое расстояние равно 3 и значит код исправляет одну ошибку. Этот код называется кодом Хэмминга, далее будем его обозначать H n . Параметры кода Хэмминга: [n = 2 m − 1, k = n − log(n + 1), d = 3], m = log(n + 1) (здесь и всюду далее log(·) является двоичным логарифмом, если не оговорено особо). Утверждение 2. Код Хэмминга H n является совершенным кодом, исправляю- щим одну ошибку. Доказательство. Код H n исправляет одну ошибку (по определению кода). По построению его мощность равна |H n | = 2 n−m = 2 n n + 1 , где m = log(n + 1). Следовательно, он достигает границы Хэмминга (см. теорему 2) и потому является совершенным. N Утверждение 3. Код Хэмминга единствен с точностью до изоморфизма. 1.3. Код Хэмминга и его свойства 15 1.3.2. Примеры кодов Хэмминга длины 7 Рассмотрим три различных представления кода Хэмминга длины 7. 1. Код Хэмминга длины 7 задан проверочной матрицей в каноническом виде (см. [1], гл. 1), т. е. проверочная матрица имеет вид H = 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 . 2. Код Хэмминга длины 7 в циклическом виде. Определение. Линейный код C длины n называется циклическим, если для любого кодового слова x = (x 1 , x 2 , . . . , x n ) слово (x 2 , x 3 , . . . , x n , x 1 ) принадлежит коду C. Проверочная матрица кода Хэмминга длины 7 в циклическом представлении име- ет вид: H = 0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 . 3. Во многих случаях полезно определять код Хэмминга через проверочную мат- рицу, заданную в лексикографическом виде H = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 , т. е. столбцы проверочной матрицы записаны в лексикографическом порядке возрас- тания двоичных представлений натуральных чисел. 1.3.3. Декодирование кода Хэмминга Код Хэмминга допускает самое простое декодирование. Рассмотрим представле- ние кода Хэмминга H n посредством проверочной матрицы, столбцы которой записа- ны в лексикографическом порядке: H m = [B(1), B(2), . . . , B(n)], здесь H m – проверочная матрица кода H n , m = log(n + 1), B(i) – двоичное пред- ставление числа i. Используя эту проверочную матрицу H m , можно определить код Хэмминга следующим образом: H n = { x = (x 1 , . . . , x n ) : x ∈ E n , n X i=1 B(i) · x i = 0 m }. Определение. Вектор S y = Hy T , где H — проверочная матрица линейного кода, называется синдромом вектора y. 16 Глава 1. Линейные коды Пусть в канале связи при передаче вектора x произошла одна ошибка в i-й коор- динате и получен вектор y. Воспользовавшись тем, что для любого кодового слова x кода H n выполняется Hx T = 0 m , найдем синдром вектора y: S y = Hy T = Hx T + He T i = He T i = B(i). Синдром S y равен столбцу, номер которого i является номером ошибочной коор- динаты вектора y. Здесь e i – двоичный вектор длины n с единицей только в i-й координате. Позднее (см. гл. 4, подразд. 4.5.1.) будет рассмотрен пример кода Хэмминга над полем Галуа GF (q) для произвольного q = p m , где p – любое простое число. Упражнение 11. Доказать утверждение 3. 1.4. Способы построения новых кодов Здесь рассмотрим несколько общих способов построения кодов, как линейных, так и нелинейных. В случае построения линейных кодов их параметры будут заключены в квадратные скобки, в случае нелинейных кодов – в круглые скобки. 1. Метод комбинирования кодов Теорема 8. Пусть G 1 , G 2 – порождающие матрицы для [n 1 , k, d 1 ] и [n 2 , k, d 2 ] – кодов соответственно. Тогда коды с порождающими матрицами µ G 1 0 0 G 2 ¶ и ¡ G 1 | G 2 ¢ представляют собой [n 1 + n 2 , 2k, min{d 1 , d 2 }]- и [n 1 + n 2 , k, d]-коды соответственно, причем d > d 1 + d 2 . 2. Добавление общей проверки на четность Из двоичного кода C с параметрами (n, |C|, d), где d нечетно, образуем новый код C 0 с параметрами (n + 1, |C|, d + 1), называемый расширенным кодом добавляя 0 в конце каждого кодового слова C четного веса и добавляя 1 в конце каждого кодового слова нечетного веса. Все кодовые слова кода C 0 имеют, очевидно, четный вес. Код C 0 удовлетворяет общему уравнению проверки на четность x 1 + x 2 + . . . + x n+1 = 0. Для линейных кодов проверочная матрица кода C 0 имеет вид 1 . . . 1 0 H 0 , где H – проверочная матрица исходного кода C. Такой код называется расширенным кодом. 1.4. Способы построения новых кодов 17 3. Выкалывание кодовых координат Выкалывание кодовых координат представляет собой удаление одной и более ко- ординат во всех кодовых словах. Если исходный код C имел параметры: (n, |C|, d), то код C 0 , полученный выкалыванием одной координаты из C, имеет следующие па- раметры: (n − 1, |C 0 |, d 0 ), где |C 0 | ≤ |C|, d − 1 ≤ d 0 ≤ d (заметим, что |C| = |C 0 |, если d > 1). 4. Код с выбрасыванием Код с выбрасыванием получается из исходного удалением всех слов нечетного (или четного) веса. Из кода с параметрами (n, k, d) получается код (n, k 0 , d 0 ), где k 0 ≤ k, d 0 ≥ d и часто d 0 > d (например, если d — нечетное и удалены все слова нечетного веса). Вообще говоря, можно рассматривать коды с выбрасыванием слов некоторого веса, например, малого или большого. 5. Пополнение кода Пополнение кода C с параметрами [n, k, d] добавлением новых слов представляет собой следующее: если в E n найдется вектор a такой, что d(C, a) ≥ d, то добавим к исходному коду множество C + a. При этом мы получим код той же длины n, размерности k + 1. Упражнение 12. Оценить кодовое расстояние полученного кода. 6. Укорочение кода Укорочение кода состоит в следующем: а) выбираем все кодовые слова, у которых координата i равна 0 (либо 1). Как правило, выбирается более мощная часть кодовой матрицы с фиксированной коор- динатой i, если таковой нет, как, например, в линейных кодах, то выбираются все кодовые слова, у которых координата i равна 0; б) удаляем эту координату в выбранных словах. Из кода C с параметрами (n, |C|, d) получается (n − 1, |C 0 |, d 0 )-код C 0 , где |C 0 | ≥ |C|/2, d 0 ≥ d. Упражнение 13. Построить расширенный код Хэмминга длины 8 добавлением общей проверки на четность. Доказать, что код имеет расстояние 4, обнаруживает 2 ошибки и исправляет одну ошибку. Конструкция Плоткина Рассмотрим еще один эффективный способ построения кодов, который позволя- ет, имея в качестве стартовых коды малых длин с оптимальными или близкими к оптимальным параметрами, строить бесконечные серии кодов с такими же хороши- ми параметрами. В дальнейшем нам потребуется следующее нетрудно доказываемое утверждение. 18 Глава 1. Линейные коды Утверждение 4. Для любых векторов x и y из E n справедливо w(x + y) ≥ w(x) − w(y). Теорема 9 (Плоткин М., 1960, см. [1]). Пусть C и D — двоичные (n, M 1 , d 1 ) и (n, M 2 , d 2 )-коды соответственно. Тогда множество C 2n = {(x, x + y) : x ∈ C, y ∈ D} является (2n, M 1 · M 2 , d = min{2d 1 , d 2 })-кодом. Доказательство. Пусть u = (x, x+y), v = (x 0 , x 0 +y 0 ) — произвольные различные кодовые слова кода C 2n , где x, x 0 ∈ C, y, y 0 ∈ D. Если y = y 0 , то d(u, v) = d((x, x), (x 0 , x 0 )) = 2d(x, x 0 ) ≥ 2d 1 . Пусть y 6= y 0 , тогда, используя утверждение 4, получаем d(u, v) = w(x − x 0 ) + w(x + y − x 0 − y 0 ) = = w(x − x 0 ) + w((y − y 0 ) + (x − x 0 )) ≥ ≥ w(x − x 0 ) + w(y − y 0 ) − w(x − x 0 ) = w(y − y 0 ) = d 2 . N Упражнение 14. Доказать теорему 8. Упражнение 15. Найти порождающую матрицу расширенного кода Хэмминга длины 16, построенного с помощью конструкции Плоткина. Какие коды для этого нужно использовать? 1.5. Теорема Глаголева В этом разделе множество строк порождающей матрицы кода будем называть базовым множеством. Для доказательства теоремы Глаголева потребуется следую- щий несложно доказываемый факт (см. также п. 5 предыдущего раздела). Лемма 1. Если G — линейный код с кодовым расстоянием d и если найдется такой вектор x, что d(G, x) ≥ d, то множество G ∪ (G + x) является линейным кодом с кодовым расстоянием d. Теорема 10 (Глаголев В. В., 1971). Для любого двоичного линейного [n, k, d]-кода C существует линейный код C 0 с теми же параметрами такой, что его базовое множество состоит из кодовых слов минимального веса d. 1.5. Теорема Глаголева 19 Доказательство. В качестве базового множества рассмотрим множество T d ∪ T d+1 ∪ . . . ∪ T d+p кода C. Здесь T d — максимальное линейно независимое множество кодовых слов веса d; T d+1 — множество кодовых слов веса d + 1, которое может быть выбрано в коде C так, что T d ∪ T d+1 — максимальное линейно независимое множество кодовых слов веса не более d + 1. Аналогично выбираем остальные множества вплоть до T d+p кодовых слов веса d+p для некоторого p. Таким образом код C совпадает с линейной оболочкой множества T d ∪ T d+1 ∪ . . . ∪ T d+p , т. е. C =< T d ∪ T d+1 ∪ . . . ∪ T d+p > . Рассмотрим произвольный вектор y из T d+1 . Докажем, что расстояние между y и любым кодовым словом из T d больше d. Пусть это неверно и найдется вектор z ∈ T d такой, что d(y, z) = d. Тогда w(y + z) = d и в силу линейности кода C имеем y + z ∈ C. С другой стороны, в силу линейной независимости множества T d ∪ T d+1 справедливо y + z / ∈ T d . Следовательно, получили подмножество T d ∪ (y + z) в коде C, которое является линейно независимым множеством кодовых слов веса d и имеет мощность больше мощности множества T d , что противоречит выбору множества T d Следовательно, d(T d , y) ≥ d + 1. (1.4) Возьмем любой вектор y 0 веса d, предшествующий вектору y, т. е. y 0 ≺ y. Это означает, что все единичные координаты вектора y 0 находятся среди единичных ко- ординат кодового слова y. Используя неравенство (1.4), получаем d(T d , y) > d(T d , y 0 ) ≥ d. Рассмотрим множество T d ∪ (T d + y 0 ). Согласно лемме 1, его линейная оболочка явля- ется линейным кодом с кодовым расстоянием d. Далее аналогичным образом в тени некоторого кодового слова множества T d+1 найдем вектор y 00 и рассмотрим множе- ство T d ∪ {y 0 , y 00 }, которое позволяет построить новый линейный код с расстоянием d и т. д., переходя от множества T d+1 к множеству T d+2 и далее до множества T d+p , не более чем за k шагов построим линейный [n, k, d]-код C 0 с базовым множеством, состоящим из кодовых слов минимального веса d. N Замечание. В 1992 г. Ю. Симонис получил аналогичный результат для q-значных линейных кодов над GF (q). Следующее утверждение вытекает из теоремы Глаголева и утверждения 3 о един- ственности кода Хэмминга. Следствие 1. Для произвольного кода Хэмминга существует базовое множе- ство, состоящее из кодовых слов веса 3. Упражнение 16. Доказать лемму 1. Глава 2 Декодирование 2.1. Декодирование двоичных кодов Пусть сообщение u = (u 1 , . . . , u k ) закодировано кодовым словом x = (x 1 , . . . , x n ), которое передается по каналу связи с шумом. Принятый вектор y = (y 1 , . . . , y n ) может отличаться от x. Введем вектор ошибок e = y − x = (e 1 , . . . , e n ), где e i = 0 с вероятностью 1 − p, e i = 1 с вероятностью p (исказился i-й символ), p — произвольное число, удовлетворяющее 0 < p < 1/2. Задача декодера — решить на основании принятого слова y, какое сообщение u или, что, как правило, удобнее, какое кодовое слово x было передано. Если декодер найдет слово e, то легко вычислить кодовое слово x = y − e. Но декодер часто не может определить в точности, чему равен вектор ошибок e. В этом случае его стратегия заключается в выборе наиболее вероятного вектора ошибок e. Опишем декодирование в ближайшее кодовое слово или декодирование по мак- симуму правдоподобия (для двоичного симметричного канала связи эти методы де- кодирования совпадают, поскольку метрика Хэмминга согласована с двоичным сим- метричным каналом). Поскольку ошибки происходят независимо с вероятностью p, то для вектора ошибок e длины n имеем P {e = (000 . . . 0)} = (1 − p) n , P {e = (010 . . . 0)} = p · (1 − p) n−1 , . . . P {e = v, w(v) = k} = p k · (1 − p) n−k , где e — вектор ошибки длины n. Так как p < 1/2, то 1 − p > p и, очевидно, справедливо (1 − p) n > p · (1 − p) n−1 > . . . > p k · (1 − p) n−k > . . . . Другими словами, фиксированный вектор ошибок веса 1 более вероятен, чем век- тор ошибок веса 2, и т. д. Отсюда напрашивается стратегия декодирования: y декоди- руется в ближайшее кодовое слово x или, что то же самое, выбирается вектор ошибок e наименьшего веса. Такая процедура декодирования называется декодированием по 20 2.2. Декодирование линейных кодов 21 максимуму правдоподобия (т. е. в выборе наиболее вероятного вектора ошибок e для данного принятого вектора y) или декодированием в ближайшее кодовое слово. Для кодов, мощность которых невелика, допустимо декодирование полным пере- бором, но, очевидно, что эта стратегия не является эффективной. Одной из главных целей теории корректирующих кодов является конструирование кодов с эффектив- ными процедурами декодирования. 2.2. Декодирование линейных кодов 2.2.1. Стандартное расположение. Синдром Для линейных кодов могут применяться особые процедуры декодирования с ис- пользованием синдромов и таблицы стандартного расположения. Пусть C — линейный двоичный [n, k]-код (все дальнейшие рассуждения в этом пункте справедливы для линейных кодов над полем из q ≥ 2 элементов). Для любого вектора a множество a + C = {a + x | x ∈ C} называется смежным классом (или сдвигом) кода C. Каждый смежный класс со- держит 2 k векторов, два вектора a, b принадлежат одному и тому же смежному классу тогда и только тогда, когда a − b ∈ C. Любые два смежных класса либо не пересекаются либо совпадают (частичное пересечение невозможно). Этот факт легко доказывается от противного. Таким образом, n-мерный единичный куб E n можно разбить на классы смежности по линейному коду C: E n = C ∪ (a 1 + C) ∪ . . . ∪ (a m + C), где m = 2 n−k − 1. Вектор y, принятый декодером, попадает в некоторый i-й класс смежности y ∈ a i + C, т. е. y = a i + x для некоторого x ∈ C. Если было передано слово x 0 , то вектор ошибок вычисляется как e = y − x 0 = a i + x − x 0 = a i + x 00 ∈ a i + C, т. е. вектор ошибок принадлежит тому же i-му классу смежности. Таким образом, если получили вектор y из i-го класса смежности, то возможными векторами ошибок будут все векторы i-го смежного класса. Отсюда вытекает следующая стратегия де- кодера: из смежного класса, содержащего вектор y, выбирается вектор e наименьшего веса. Если таких векторов несколько, то выбирается любой из них. Далее произво- дится декодирование y как x = y − e. Вектор минимального веса из смежного класса называется лидером смежного класса. Опишем таблицу, называемую стандартным расположением для кода. Стандарт- ное расположение — удобный способ описания работы декодера. В первую строку 22 Глава 2. Декодирование таблицы помещаются сообщения, во вторую — кодовые векторы, причем в первом столбце стоит нулевой вектор: x 1 = 0, x 2 , . . . , x 2 k . В третью строку под нулевым вектором помещается лидер a 1 некоторого класса смежности по коду C и строка заполняется таким образом, чтобы под кодовым словом x i стояло слово a 1 + x i . Сле- дующие строки заполняются аналогично. Процесс продолжается до тех пор, пока не исчерпаются все векторы из E n Сообщение u 1 u 2 · · · u 2 k Синдром Код x 1 = 0 x 2 · · · x 2 k S 0 Первый смежный класс a 1 a 1 + x 2 · · · a 1 + x 2 k S a 1 Второй смежный класс a 2 a 2 + x 2 · · · a 2 + x 2 k S a 2 · · · · · · · · · · · · · · · · · · m = (2 n−k − 1)-й смежный класс a m a m + x 2 · · · a m + x 2 k S a m По построению в таблице стандартного расположения в строках находятся классы смежности с лидерами классов смежности, расположенными в первом столбце. В последнем столбце записываются синдромы лидеров. Сначала рассмотрим процесс декодирования без использования столбца синдромов. Пример 1. Рассмотрим пример линейного [4, 2]-кода (см. [1], с. 26) с порождаю- щей матрицей G = · 1 0 1 1 0 1 0 1 ¸ . Таблица стандартного расположения без столбца синдромов для этого кода имеет вид Сообщение 00 10 01 11 Код 0000 1011 0101 1110 Первый смежный класс 1000 0011 1101 0110 Второй смежный класс 0100 1111 0001 1010 Третий смежный класс 0010 1001 0111 1100 |