В теории кодирования , блочные коды большое и важное семейство кодов с исправлением ошибок , которые кодируют данные в блоках. Существует огромное количество примеров блочных кодов, многие из которых имеют широкий спектр практических применений. Абстрактное определение блочных кодов концептуально полезно, поскольку позволяет теоретикам кодирования, математикам и компьютерным специалистам изучать ограничения всех блочных кодов единым способом. Такие ограничения часто принимают форму границ, которые связывают различные параметры блочного кода друг с другом, такие как его скорость и его способность обнаруживать и исправлять ошибки.
Примеры блочных кодов Рида-Соломона , коды Хэмминга , коды Адамара , коды расширителей , коды Голея , а также коды Рида-Мюллера . Эти примеры также относятся к классу линейных кодов , поэтому они называются линейными блочными кодами . В частности, эти коды известны как алгебраические блочные коды или циклические блочные коды, поскольку они могут быть сгенерированы с использованием логических полиномов.
Алгебраические блочные коды обычно жестко декодируются с использованием алгебраических декодеров. [ жаргон ]
Термин « блочный код» может также относиться к любому коду с исправлением ошибок, который действует на блок биты входных данных для производства биты выходных данных . Следовательно, блочный кодер - это устройство без памяти . В соответствии с этим определением коды, такие как турбокоды , сверточные коды с завершением и другие итеративно декодируемые коды (турбоподобные коды), также будут считаться блочными кодами. Сверточный кодер без завершения может быть примером неблочного (без кадра) кода, который имеет память и вместо этого классифицируется как древовидный код .
В этой статье рассматриваются «алгебраические блочные коды».
Код блока и его параметры
Коды с исправлением ошибок используются для надежной передачи цифровых данных по ненадежным каналам связи, подверженным шумам в канале . Когда отправитель хочет передать, возможно, очень длинный поток данных с использованием блочного кода, отправитель разбивает поток на части некоторого фиксированного размера. Каждая такая часть называется сообщением, и процедура, заданная блочным кодом, кодирует каждое сообщение индивидуально в кодовое слово, также называемое блоком в контексте блочных кодов. Затем отправитель передает все блоки получателю, который, в свою очередь, может использовать некоторый механизм декодирования, чтобы (надеюсь) восстановить исходные сообщения из возможно поврежденных полученных блоков. Производительность и успех всей передачи зависят от параметров канала и блочного кода.
Формально блочный код - это инъективное отображение
- .
Здесь, конечное и непустое множество и а также целые числа. Значение и значение этих трех параметров и других параметров, связанных с кодом, описаны ниже.
Алфавит Σ
Кодируемый поток данных моделируется как строка над некоторым алфавитом. . Размер алфавита часто записывается как . Если, то блочный код называется двоичным блочным кодом. Во многих приложениях полезно учитыватьбыть главной силой и определятьс конечным полем .
Длина сообщения k
Сообщения - это элементы из , то есть строки длины . Следовательно, числоназывается длиной сообщения или размером блочного кода.
Длина блока n
Длина блока кода блока - это количество символов в блоке. Следовательно, элементы из строки длины и соответствуют блокам, которые могут быть приняты получателем. Поэтому их еще называют принятыми словами. Если для какого-то сообщения , тогда называется кодовым словом .
Ставка R
Скорость блочного кода определяются как отношение между его длиной сообщения и его длиной блока:
- .
Большая скорость означает, что количество фактического сообщения на переданный блок велико. В этом смысле скорость измеряет скорость передачи и количествоизмеряет накладные расходы, возникающие из-за кодирования с помощью блочного кода. Это простой теоретический факт, что скорость не может превышатьпоскольку данные, как правило, не могут быть сжаты без потерь. Формально это следует из того, что код является инъективным отображением.
Расстояние d
Расстояние или минимальное расстояние d блочного кода минимальное количество положений , в которых любые два различных кодовых слова отличаются, и относительное расстояние это дробь . Формально для полученных слов, позволять обозначим расстояние Хэмминга между а также , то есть количество позиций, в которых а также различаются. Тогда минимальное расстояние кода определяется как
- .
Поскольку любой код должен быть инъективным , любые два кодовых слова не будут согласовываться по крайней мере в одной позиции, поэтому расстояние любого кода не менее. Кроме того, расстояние равно минимальному весу для линейных блочных кодов, потому что:
- .
Большее расстояние позволяет больше исправлять и обнаруживать ошибки. Например, если мы рассматриваем только ошибки, которые могут изменить символы отправленного кодового слова, но никогда не стираем и не добавляем их, то количество ошибок - это количество позиций, в которых отправленное кодовое слово и полученное слово отличаются. Код с расстоянием d позволяет приемнику обнаруживать до ошибки передачи с момента изменения позиции кодового слова никогда не могут случайно дать другое кодовое слово. Кроме того, если не болеевозникают ошибки передачи, приемник может однозначно декодировать полученное слово в кодовое слово. Это потому, что каждое полученное слово имеет не более одного кодового слова на расстоянии.. Если больше чемвозникают ошибки передачи, приемник не может однозначно декодировать полученное слово в целом, поскольку может быть несколько возможных кодовых слов. Один из способов для приемника справиться с этой ситуацией - использовать декодирование списка , при котором декодер выводит список всех кодовых слов в определенном радиусе.
Популярные обозначения
Обозначение описывает блочный код по алфавиту размера , с длиной блока , длина сообщения , и расстояние . Если блочный код является линейным блочным кодом, то квадратные скобки в обозначениииспользуются для представления этого факта. Для двоичных кодов с, индекс иногда опускается. Для кодов с разделением на максимальное расстояние расстояние всегда равно, но иногда точное расстояние неизвестно, нетривиально доказать или указать, или нет необходимости. В таких случаях-компонент может отсутствовать.
Иногда, особенно для неблочных кодов, обозначение используется для кодов, содержащих кодовые слова длины . Для блочных кодов с сообщениями длины над алфавитом размера , это число будет .
Примеры
Как упоминалось выше, существует огромное количество кодов с исправлением ошибок, которые на самом деле являются блочными кодами. Первым кодом исправления ошибок был код Хэмминга (7,4) , разработанный Ричардом У. Хэммингом в 1950 году. Этот код преобразует сообщение, состоящее из 4 бит, в кодовое слово из 7 бит, добавляя 3 бита четности. Следовательно, этот код является блочным кодом. Оказывается, это также линейный код и расстояние 3. В сокращенных обозначениях, приведенных выше, это означает, что код Хэмминга (7,4) является код.
Коды Рида – Соломона представляют собой семейство коды с а также будучи главной державой . Коды рангов - это семейство коды с . Коды Адамара представляют собой семейство коды с а также .
Свойства обнаружения и исправления ошибок
Кодовое слово можно рассматривать как точку в -размерное пространство и код это подмножество . Код имеет расстояние Значит это , в шаре Хэмминга с центром в с радиусом , который определяется как набор -мерные слова, расстояние Хэмминга которых до не более чем . По аналогии, с (минимальным) расстоянием обладает следующими свойствами:
- может обнаружить ошибки: потому что кодовое слово - единственное кодовое слово в шаре Хэмминга с центром в самом себе и радиусом , нет шаблонов ошибок или меньшее количество ошибок может изменить одно кодовое слово на другое. Когда приемник обнаруживает, что полученный вектор не является кодовым словом, ошибки обнаружены (но нет гарантии исправления).
- может исправить ошибки. Потому что кодовое слово - единственное кодовое слово в шаре Хэмминга с центром в самом себе и радиусом , два шара Хэмминга с центрами в двух разных кодовых словах соответственно с обоими радиусами не пересекаются друг с другом. Следовательно, если мы рассматриваем исправление ошибок как нахождение кодового слова, наиболее близкого к принятому слову, пока количество ошибок не более , в шаре Хэмминга есть только одно кодовое слово с центром в с радиусом , поэтому все ошибки можно исправить.
- Для декодирования при наличии более ошибок, может использоваться декодирование по списку или декодирование по методу максимального правдоподобия .
- может исправить стирания . Под стиранием это означает, что положение стертого символа известно. Исправление может быть достигнуто-проходящее декодирование: В проходя стертую позицию, заполняется символ и исправление ошибок. Должен быть один проход, что количество ошибок не более чем и поэтому стирания можно исправить.
Нижняя и верхняя границы блочных кодов
Семейство кодов
называется семейством кодов , где является код с монотонным возрастанием .
Скорость семейства кодов C определяется как
Относительное расстояние семейства кодов C определяется как
Чтобы изучить взаимосвязь между а также известен набор нижних и верхних границ блочных кодов.
Граница Хэмминга
Граница синглтона
Ограничение Синглтона заключается в том, что сумма скорости и относительного расстояния блочного кода не может быть намного больше 1:
- .
Другими словами, каждый блочный код удовлетворяет неравенству . Коды Рида – Соломона являются нетривиальными примерами кодов, удовлетворяющих одноэлементной оценке равенства.
Граница Плоткина
Для , . Другими словами,.
В общем случае справедливы следующие оценки Плоткина для любых с расстоянием d :
- Если
- Если
Для любого q -арного кода с расстоянием,
Граница Гилберта – Варшамова
, где , является q- мерной функцией энтропии.
Джонсон связан
Определять .
Позволятьмаксимальное количество кодовых слов в шаре Хэмминга радиуса e для любого кодарасстояния d .
Затем у нас есть граница Джонсона :, если
Элиас – Бассалыго
Сферы и решетки
Блочные коды связаны с проблемой упаковки сфер, которой на протяжении многих лет уделялось некоторое внимание. В двух измерениях это легко визуализировать. Возьмите связку монет на столе и сдвиньте их вместе. В результате получился шестиугольник, похожий на пчелиное гнездо. Но блочные коды полагаются на большее количество измерений, которые трудно визуализировать. Мощный код Голея, используемый для связи в дальнем космосе, использует 24 измерения. При использовании в качестве двоичного кода (что обычно бывает) размеры относятся к длине кодового слова, как определено выше.
Теория кодирования использует модель N- мерной сферы. Например, сколько пенни можно упаковать в круг на столе или в 3-х измерениях, сколько шариков можно упаковать в глобус. Другие соображения относятся к выбору кода. Например, упаковка шестиугольника в прямоугольную коробку оставит пустые места по углам. По мере увеличения размеров процент пустого пространства становится меньше. Но при определенных размерах упаковка занимает все пространство, и эти коды являются так называемыми совершенными кодами. Таких кодов очень мало.
Другое свойство - количество соседей, которые может иметь одно кодовое слово. [1] Опять же, рассмотрим в качестве примера гроши. Сначала упаковываем пенни в прямоугольную сетку. У каждого пенни будет 4 ближайших соседа (и 4 на дальних углах). В шестиугольнике у каждой копейки будет 6 ближайших соседей. Соответственно, в трех и четырех измерениях максимальную упаковку дают 12-гранная и 24-ячеечная с 12 и 24 соседями соответственно. Когда мы увеличиваем размеры, количество ближайших соседей увеличивается очень быстро. В общем, ценность дается числами поцелуев .
В результате увеличивается количество способов, которыми шум заставляет приемник выбирать соседа (следовательно, возникает ошибка). Это фундаментальное ограничение блочных кодов, да и вообще всех кодов. Может быть труднее вызвать ошибку для одного соседа, но количество соседей может быть достаточно большим, так что на самом деле страдает общая вероятность ошибки. [1]
Смотрите также
- Емкость канала
- Теорема Шеннона – Хартли.
- Шумный канал
- Расшифровка списка [1]
- Упаковка сфер
Рекомендации
- ^ a b c Кристиан Шлегель и Ланс Перес (2004). Решетки и турбо-кодирование . Wiley-IEEE. п. 73. ISBN 978-0-471-22755-7.
- Дж. Х. ван Линт (1992). Введение в теорию кодирования . GTM . 86 (2-е изд.). Springer-Verlag. п. 31 . ISBN 3-540-54894-7. CS1 maint: обескураженный параметр ( ссылка )
- FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. п. 35 . ISBN 0-444-85193-3. CS1 maint: обескураженный параметр ( ссылка )
- В. Хаффман; В.Плесс (2003). Основы кодов исправления ошибок . Издательство Кембриджского университета. ISBN 978-0-521-78280-7. CS1 maint: обескураженный параметр ( ссылка )
- С. Линь; DJ мл. Костелло (1983). Кодирование с контролем ошибок: основы и приложения . Прентис-Холл. ISBN 0-13-283796-X.
Внешние ссылки
- Чаран Лэнгтон (2001) Концепции кодирования и блочное кодирование