А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 2
Текст из файла (страница 2)
Если нового слова выбрать нельзя, это значит, что всёпространство (в котором элементов) полностью покрыто шарами, каждый из которых состоит из (2, ) элементов. Наше предположениегарантирует, что при этом имеется как минимум шаров, что и требуется.Переходя к логарифмам, условие можно записать так: + log (2, ) 6 1(для простоты записи мы немного усилили условие и тем самым ослабилиутверждение о существовании кода, отбросив вычитание единицы). Этонеравенство называют границей Гилберта. Не следует путать автора этойоценки Эдгара Гилберта (Edgar N. Gilbert) со знаменитым математикомДавидом Гильбертом (David Hilbert).Размер шараОбе эти оценки включают в себя число элементов в шаре, поэтомуполезно иметь для этого числа хотя бы приближённую формулу.
Дляслучая = 2 число элементов в шаре радиуса равно сумме биномиальных коэффициентов + + . . . + .При 6 /2 (в основном нас интересует этот случай, так как шаровбольшего радиуса даже и два не поместится) слагаемые в этой сумме возрастают слева направо и (с точностью до полиномиальных от множителей) можно ограничиться последним слагаемым. Число сочетаний можнооценить с помощью формулы Стирлинга. В нашем случае достаточно использовать довольно грубое приближение для факториала: ! ≈ (/ )с точностью до полиномиальных (по ) множителей.
Подставляя его вформулу = − , получаем, что последнее слагаемое в нашей суммеи вся сумма могут быть записаны в видеpoly( )2 ,01!!()!()82. âÁÚÏ×ÙÅ ÏÃÅÎËÉгде = / , а ( ) | энтропия Шеннона распределения (, 1 − ),которая определяется как ( ) = log 1 + (1 − ) log 1 −1 .Для произвольного формула имеет вид (, ) = poly( ) ,где = / , а ( ) = log 1 + (1 − ) log 1 −1 + log ( − 1).Выражение в квадратной скобке, как и раньше, соответствует выбору неболее чем позиций, в которых есть отличия (от центра шара), нопоявляется ещё один член: в каждой из этих позиций может стоятьлюбой из − 1 символов (не считая теперешнего).()ГрафикиПолезно изобразить границы Хэмминга и Гилберта на одном графике. По горизонтали будем откладывать кодовое расстояние (примерноравное 2 , удвоенному числу исправляемых ошибок) в долях ; по вертикали | коэффициент полезного действия кода (отношение / , где | число кодируемых символов, а | длина кода).Ограничимся случаем = 2 и будем использовать приближённуюформулу для объёма шара.Необходимое условие существование кода, исправляющего ошибок(граница Хэмминга): + (/ ) 6 1 + (log / ).Достаточное условие существования кода с расстоянием не меньше + (/ ) 6 1 − (log / ).Формулы эти похожи, но только и отличаются примерно в два раза.Поэтому график для границы Хэмминга получается двукратным растяжением графика для границы Гилберта по горизонтали (рис.
1).93. óÌÕÞÁÊÎÙÅ ËÏÄÙ1 /кода нет1/2кодесть?1/21 /Рис. 1. Границы Хэмминга и Гилберта.По этой картинке можно определить, скажем, что кода с коэффициентом полезного действия 1/2 и расстоянием в /3 не существует |соответствующая точка лежит выше границы Хэмминга. С другой стороны, код с коэффициентом полезного действия 1/8 и расстоянием /4 (итем самым допускающим исправление /8 ошибок) существует | соответствующая точка лежит ниже границы Гилберта. (Всё сказанное относится к достаточно большим , так как мы пренебрегали членами порядка (log / ).)Что происходит между этими границами | один из основных вопросов теории кодирования, до сих пор не решённый полностью (несмотряна множество частичных результатов).3.
Случайные кодыГраницу Гилберта можно достичь и другими способами. В этом разделе мы используем случайный код, а в следующем разделе | линейный.Пусть фиксировано некоторое число . Будем выбирать кодовыхслов , . . . , случайно среди равновероятных элементов ˚ . Приэтом мы считаем все , . . . , независимыми.
(В частности, вероятностьсовпадения и при ̸= отлична от нуля, хотя и мала.)Для фиксированного ∈ {1, . . . , } рассмотрим вероятность того,что в шар радиуса 2 с центром попадут другие кодовые слова. Ве11104. ìÉÎÅÊÎÙÅ ËÏÄÙроятность попадания с данным равна (2, )/ (доле пространства, занимаемой шаром радиуса 2 ); вероятность того, что хотя бы одно (при ̸= ) попадёт в этот шар, не больше (2, )/ . Будем называть те , при которых в шар с центром в попали другие , «плохими». Тогда вероятность каждого оказаться плохим не больше (2, )/ . Поэтому математическое ожидание числа плохих не больше (2, )/ , а математическое ожидание доли плохих (среди всех чисел 1, . . . , ) | не больше (2, )/ .Предположим теперь, что (2, )6 1/ 22(вдвое меньшее число кодовых слов, чем допускает граница Гилберта).Тогда математическое ожидание доли плохих не больше 1/2.Итак, если выбирать кодовые слова , . .
. , случайно, то числоплохих в среднем (усреднение по выбору случайного кода) будет меньше /2. Следовательно , среди всех возможных выборов кодовых словсуществует такой, при котором эта доля не больше 1/2.Зафиксировав один из таких вариантов и выкинув плохие кодовые слова (их не более половины), мы получим код с расстоянием не менее 2 +1,который всего лишь в четыре раза хуже (по числу слов | мы начали свдвое меньшего числа, да ещё отбросили половину), чем построенныйранее. Уменьшение количества кодовых слов в четыре раза означает, чтомы уменьшаем (число битов, определяющих кодовое слов) лишь на двабита.114. Линейные кодыЕсли есть степень простого числа, то (как известно из алгебры)существует поле F из элементов.
В этом случае можно считать, что˚ = F , а слова образуют векторное пространство (размерности или ) над F . В этой ситуации возникает понятие линейного кода. Такой1 Этот способ вероятностного доказательства существования часто применяется в комбинаторике: чтобы установить, что существует вариант, при котором какая-то величинавелика (или мала), мы доказываем, что её среднее значение по какому-то распределениювероятностей велико (или мало). Например, вершины любого графа можно так раскрасить вдва цвета, чтобы как минимум половина рёбер соединяла вершины разных цветов.
В самомделе, при случайной раскраске каждое ребро оказывается «разноцветным» с вероятностью1/2 и потому средняя доля разноцветных рёбер равна 1/2.114. ìÉÎÅÊÎÙÅ ËÏÄÙкод представляет собой линейное (над F ) отображение F → F . Этоотображение задаётся матрицей размера × , элементы которой принадлежат полю F .Множество всех кодовых слов линейного кода (образ этого отображения) представляет собой подпространство в F . В силу линейностиокрестности всех кодовых слов устроены одинаково (отличаются сдвигом). Поэтому минимальное расстояние линейного кода можно измерятьв любой точке, в частности, в нуле: оно равно минимально возможномучислу ненулевых координат в ненулевом кодовом слове.Таким образом, для построения линейного кода с расстоянием больше 2 достаточно указать -мерное подпространство в пространствеF , все ненулевые векторы которого содержат более 2 ненулевых координат (не попадают в шар радиуса 2 с центром в нуле).
Само кодовоеотображение F → после этого можно выбрать любым, лишь бы онобыло изоморфизмом линейных пространств.Чтобы построить искомый линейный код, будем добавлять в базисподпространства вектор за вектором, следя за тем, чтобы кодовое расстояние оставалось больше 2 . Пусть уже есть базисных векторов, которые порождают некоторое подпространство. Новый (добавляемый) базисный вектор должен быть на расстоянии более 2 от всех векторовподпространства; это, как легко понять, гарантирует, что и после егодобавления расстояние между любыми двумя векторами останется больше 2 . Другими словами, новый вектор должен лежать вне объединения шаров радиуса 2 .Таким образом, для получения -мерного подпространства достаточно выполнения неравенства − (2, ) < .Эту оценку называют границей Варшамова { Гилберта.
Она чуть лучшеоценки в границе Гилберта (там было − 1, а теперь − ), но это рассуждение годится лишь при некоторых (степенях простых чисел). Пристремлении к бесконечности оценки Гилберта и Варшамова { Гилбертадают одинаковые асимптотические оценки для отношения / .Заметим, что в случае линейного кода кодирование выполняется легко(умножение на матрицу кода), но про декодирование по-прежнему ничегохорошего сказать нельзя (хотя для некоторых линейных кодов, как мыувидим, существуют быстрые алгоритмы декодирования).Линейное подпространство размерности в пространстве F можнозадавать не только как образ линейного оператора F → F , но и как11125.
ëÏÄ èÜÍÍÉÎÇÁядро оператора F → F − , имеющего максимальный ранг ( − ). Такой оператор задаётся матрицей из − строк и столбцов. Векторстолбец высоты является кодовым словом тогда и только тогда, когда = 0 ( − уравнений с переменными; можно сказать, что эти уравнения представляют собой «контрольные суммы», которые у кодовых словдолжны равняться нулю).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
