А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 6
Текст из файла (страница 6)
А один процент блоков внешнего кода неможет сильно повлиять на его кодовое расстояние..1. При этой конструкции построение кода и кодирование не требуютперебора. Однако декодирование внутреннего кода (в тех блоках, где оноудаётся) по-прежнему требует перебора всех возможных кодовых слов.2. Построенный код легко описать безо всякого упоминания о конкатенации. В самом деле, мы делаем всё как в кодах Рида { Соломона, только берём значения (во всех точках поля) не одного многочлена ( ), адвух: многочлена ( ) и многочлена ( ).
Другими словами, мы записываем данный нам набор элементов поля в коэффициенты многочленовдважды | начиная со свободного члена и начиная с первой степени |и объединяем полученные значения.Замечания2613. ïÃÅÎËÁ ðÌÏÔËÉÎÁ13. Оценка ПлоткинаРазличие между границами Хэмминга и Гилберта особенно разительнов правой половине рис. 1: при > /2 граница Хэмминга не запрещаетсуществования кодов, а граница Гилберта не гарантирует их существования. Что же происходит на самом деле? (Речь идёт о двоичных кодах,когда ˚ = {0, 1}.)Максимальное расстояние между двумя элементами B равно . Точки, между которыми такое расстояние, отличаются во всех позициях, ипотому ясно, что три точки с попарными расстояниями найти нельзя.Более того, даже если ослабить требования и искать три точки с попарными расстояниями не меньше 0,99 , это тоже не удастся: если и отличаются от в 99% мест, то совпадает с по крайней мере в 98%мест.Аналогичное утверждение, хотя и не по столь очевидным причинам,справедливо для любой доли > 1/2..
Пусть > 1/2. Количество точек в B , попарные расстояниямежду которыми не меньше , не превосходит12 − 1 + 1 .Здесь важно, что оценка на число точек не зависит от (хотя и зависит от : чем ближе к 1/2, тем слабее оценка).леммы. Удобно вместо последовательностей нулей иединиц рассматривать последовательности единиц и минус единиц, считая их векторами в R . Определим скалярное произведение в R , положивЛеммаДоказательство(⟨ , . . . , ⟩, ⟨ , . . .
, ⟩) = ∑ .11Разница с обычным скалярным произведением в R состоит лишь в дополнительном делении на . Это технически удобно, поскольку при этомевклидова длина любого слова (которое, напомним, мы считаем векторомиз плюс-минус единиц) равна 1.Если расстояние Хэмминга между двумя кодовыми словами не меньше , то их скалярное произведение отрицательно и не больше 1 − 2 .Теперь легко получить оценку на число векторов: если имеется единичных векторов , . . .
, в евклидовом пространстве и при этомскалярное произведение любых двух из них не больше 1 − 2 , то0 6 ( + . . . + , + . . . + ) 6 + ( − 1)(1 − 2 )1112713. ïÃÅÎËÁ ðÌÏÔËÉÎÁ(имеется квадратов и (векторов), откуда− 1)попарных произведений различных − 1 6 2 1− 1 ,что и требовалось в лемме.Таком образом, если мы хотим, чтобы количество передаваемой информации росло с ростом , на исправление более чем 25% ошибок надеяться не приходится. В частности, в правой половине рис.
1 никакихинтересных кодов нет, хотя оценка Хэмминга их и не запрещает.Если требовать, чтобы кодовое расстояние было больше 50% (разрешая ему быть сколь угодно близким к 50%), то все углы между кодовымисловами будут тупыми и число точек не больше + 1, как показываетследующее простое утверждение:Если несколько векторов евклидова пространства образуют попарно тупые углы, то после удаления любого из векторов получается линейно независимая система.В самом деле, предположим, что векторы , . . . , образуют попарнотупые углы.
Покажем, что , . . . , линейно независимы. Пусть это нетак и + . . . + = 0.Вычеркнем все нулевые коэффициенты. Если оставшиеся коэффициентыимеют один знак, то умножим скалярно на и получим противоречие:сумма нескольких отрицательных скалярных произведений с коэффициентами одного знака равна нулю.Если оставшиеся коэффициенты имеют разные знаки, то разнесём ихв разные части и получим равенство + . . . = + .
. . ,где все коэффициенты положительны. Если обе части равны нулю, тосмотри выше. Если же нет, то скалярное произведение левой части направую одновременно положительно (как скалярный квадрат вектора) иотрицательно (как сумма отрицательных скалярных произведений с положительными коэффициентами). Линейная независимость доказана.Если разрешить и прямые углы (наряду с тупыми), то максимальноечисло векторов в -мерном евклидовом пространстве возрастёт до 2 .В самом деле, можно взять плюс-минус векторы базиса, их как раз 2 .Больше векторов взять не удастся:01110Если векторы в -мерном евклидовом пространстве образуют по2 .парно прямые или тупые углы, то их число не превосходит2813.
ïÃÅÎËÁ ðÌÏÔËÉÎÁВ самом деле, можно считать, что линейная оболочка векторов совпадает со всем пространством (иначе можно свести дело к меньшей размерности, рассуждая по индукции) и векторы , . . . , образуют базис.Выразим остальные (при > ) через , . . . , .. Заметим, что в таких выражениях все ненулевые коэффициенты (а в каждом из выражений они есть, поскольку ̸= 0) отрицательны.В самом деле, предположим, что это не так и в каком-то из выражений = + . . . + есть положительные . Перенесём все отрицательные коэффициенты влевую часть и получим равенство + (− ) + .
. . = + . . . ,где все коэффициенты при положительны и в правой части что-тоосталось (ведь были положительные коэффициенты). Тогда правая частьэтого равенства (а значит, и левая) отлична от нуля в силу линейной независимости векторов базиса. Произведение левой части на правую должно быть одновременно положительно (как скалярный квадрат ненулевоговектора) и неположительно (поскольку после раскрытия скобок становится суммой неположительных скалярных произведений с положительнымикоэффициентами). Противоречие..
Если общее число векторов больше 2 , то векторы при > (их не меньше + 1 штук в -мерном пространстве) линейно зависимы. Коэффициенты их нулевой линейной комбинации не могут бытьодного знака, ведь в выражениях через базисные векторы , . . . , коэффициенты отрицательны и сократиться друг с другом не могут.
Значит,есть разные знаки и можно снова разнести их по разным частям: + . . . = + . . . ,где все коэффициенты положительны. Обе части содержат хотя быодин ненулевой член и потому не равны нулю (как мы уже знаем пролинейные комбинации с коэффициентами одного знака). Поэтому скалярное произведение левой части и правой одновременно положительно (какскалярный квадрат ненулевого вектора) и неположительно (как сумманеположительных скалярных произведений с положительными коэффициентами). Противоречие.Таким образом, мы приходим к оценке (границе ) Плоткина : числокодовых слов длины с попарными расстояниями не меньше /2 непревосходит 2 .11Шаг 111Шаг 212915. ëÏÄ áÄÁÍÁÒÁ14.
Улучшение оценки СинглтонаИмея оценку Плоткина, вернёмся к рассуждению, использованномудля доказательства оценки Синглтона, и получим более сильную оценку.Будем рассматривать случай кодов в двухбуквенном алфавите.Пусть код имеет длину кодовых слов , длину кодируемого слова ирасстояние (мы будем писать для краткости «[, , ] -код»; индекс 2 |размер алфавита). Принцип Дирихле показывает, что для любого от 1до − 1 среди 2 кодовых слов можно указать 2 − кодовых слов, которыесовпадают в первых битах.
Они образуют [ −, −, ] -код (посколькупервые битов совпадают, различий приходятся на остальные − битов).Доказывая оценку Синглтона, мы брали = − 1 и замечали, чтодля полученного кода (с двумя кодовыми словами) расстояние не большедлины кодового слова: − ( − 1) > .Теперь мы можем взять меньшее , при котором у полученного кода длинакодового слова будет равна удвоенному расстоянию: − = 2, или = − 2.Согласно оценке Плоткина, число кодовых слов не превосходит удвоенной длины:2 − 6 4, или − + 2 6 log(4 ).Замечая, что 6 и деля на , получаем оценку22 + 26 1 + 4 log /.При больших последним слагаемым можно пренебречь и на рис. 1появляется новая граница (пунктир на рис.
3).Видно, что она кое-где сильнее, а кое-где слабее границы Хэмминга.15. Код АдамараОказывается, что оценка Плоткина является точной, если есть степень двойки. Соответствующий пример доставляют коды Адамара.3015. ëÏÄ áÄÁÍÁÒÁ1 /нет1/2есть?нет1/21 /Рис. 3. Улучшение границы Синглтона.Код Адамара состоит из 2 кодовых слов длины , любые два изкоторых отличаются либо ровно в половине позиций (так что соответствующие векторы ортогональны), либо во всех позициях. Код Адамарастроится при = 2 . Для этого позиции в слове будем представлять себекак вершины -мерного булева куба B , а слова | как функции B → B.Такая функция задаётся своими значениями в 2 = вершинах, и этизначения образуют слово длины , надо только фиксировать какой-либопорядок на вершинах куба.В качестве кодовых слов возьмём аффинные функции, то есть функциивида⟨ , .
. . , ⟩ ↦→ + + . . . + при , . . . , ∈ B (умножение и сложение | как в поле из двух элементов). Такая функция задаётся набором своих коэффициентов, и потомуимеется 2 = 2 аффинных функций.Две такие функции либо различаются во всех точках (если отличаютсялишь коэффициентом ), либо ровно в половине точек (образующихаффинное подпространство коразмерности 1 над полем B). Код Адамарапостроен.С точки зрения структуры евклидова пространства R , о котором мыговорили в разделе 13, кодовые слова кода Адамара являются плюс-минус базисными векторами ортонормированного базиса (замена знака соответствует добавлению единицы к аффинной функции, то есть изменению100+10113115. ëÏÄ áÄÁÍÁÒÁ ).0Итак, к настоящему времени у нас есть три явные конструкции кодовдля двухбуквенного алфавита: код Хэмминга, код Форни { Юстесена { Возенкрафта и код Адамара.
Код Хэмминга имеет коэффициент полезногодействия, близкий к 100%, но исправляет только одну ошибку. Напротив, код Адамара исправляет почти что максимально возможное числоошибок (до 25%), но зато имеет очень малый коэффициент полезногодействия. Код Форни занимает промежуточное положение: у него и доляисправляемых ошибок, и коэффициент полезного действия отделены отнуля, хотя и невелики.Для больших алфавитов ситуация лучше: там код Рида { Соломонапри подходящем выборе параметров позволяет достичь любого заданногокоэффициента полезного действия и исправляет при этом максимальновозможное (по неравенству Синглтона) число ошибок.Мы знаем, что в коде Адамара кодовое расстояние равно 50%. Однако у кода Адамара длина кодового слова экспоненциальнобольше длины исходного сообщения ( = 2 ).
Если мы хотим явно указать код, у которого кодовое расстояние приближается к 50% (и границеПлоткина), а длина кодовых слов полиномиальна (от длины кодируемогосообщения), то можно использовать каскадный код, в котором внутренним кодом является код Адамара, а внешним | код Рида { Соломона.Замечание.В самом деле, рассмотрим код Адамара с 2 кодовыми словами размера 2 . Используя его как внутренний код, мы получаем для внешнегокода алфавит из 2 символов. Для простоты записи формул пожертвуем половиной и будем использовать лишь 2 из них. Зафиксируем некоторое > 0. Внешний код Рида { Соломона будет кодировать 2 такихсимволов (блоков из битов) с помощью 2 символов (блоков), каждыйиз которых при внутреннем кодировании изображается 2 битами.(Другими словами, мы разбиваем слово из log битов, где = 2 ,на блоков размера log , и считаем каждый блок элементом F .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
