WikiDer > Код блокировки

Block code

В теория кодирования, блочные коды большая и важная семья коды с исправлением ошибок кодируют данные в блоках. Существует огромное количество примеров блочных кодов, многие из которых имеют широкий спектр практических приложений. Абстрактное определение блочных кодов концептуально полезно, поскольку позволяет теоретикам кодирования, математики, и компьютерные ученые изучить ограничения все блочные коды унифицированы. Такие ограничения часто принимают форму границы которые связывают различные параметры блочного кода друг с другом, такие как его скорость и его способность обнаруживать и исправлять ошибки.

Примеры блочных кодов: Коды Рида – Соломона, Коды Хэмминга, Коды Адамара, Коды расширителей, Коды Голея, и Коды Рида – Маллера. Эти примеры также относятся к классу линейные коды, поэтому их называют линейные блочные коды. В частности, эти коды известны как алгебраические блочные коды или циклические блочные коды, поскольку они могут быть сгенерированы с использованием логических полиномов.

Алгебраические блочные коды обычно жестко декодированный с использованием алгебраических декодеров.[жаргон]

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

В этой статье рассматриваются «алгебраические блочные коды».

Код блока и его параметры

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

Формально блочный код - это инъективный отображение

.

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

Алфавит Σ

Кодируемый поток данных моделируется как нить над некоторыми алфавит . Размер алфавита часто записывается как . Если , то код блока называется двоичный блочный код. Во многих приложениях полезно учитывать быть основная сила, и определить с конечное поле .

Длина сообщения k

Сообщения - это элементы из , то есть строки длины . Следовательно, число называется длина сообщения или же измерение блочного кода.

Длина блока п

В длина блока кода блока - это количество символов в блоке. Следовательно, элементы из строки длины и соответствуют блокам, которые могут быть приняты получателем. Поэтому их еще называют принятыми словами. для какого-то сообщения , тогда называется кодовым словом .

Оценка р

В ставка блочного кода определяется как соотношение между длиной его сообщения и длиной его блока:

.

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

Расстояние d

В расстояние или же минимальное расстояние d блочного кода - это минимальное количество позиций, в которых различаются любые два различных кодовых слова, а относительное расстояние это дробь . Формально для полученных слов , позволять обозначить Расстояние Хэмминга между и , то есть количество позиций, в которых и отличаются. Тогда минимальное расстояние кода определяется как

.

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

.

Чем больше расстояние, тем больше ошибок исправляется и обнаруживается. Например, если мы рассматриваем только ошибки, которые могут изменить символы отправленного кодового слова, но никогда не стираем и не добавляем их, то количество ошибок - это количество позиций, в которых отправленное кодовое слово и полученные слова различаются. код с расстоянием d позволяет приемнику обнаруживать до ошибки передачи с момента изменения позиции кодового слова никогда не могут случайно дать другое кодовое слово. Кроме того, если не более возникают ошибки передачи, приемник может однозначно декодировать полученное слово в кодовое слово. Это потому, что каждое полученное слово имеет не более одного кодового слова на расстоянии. . Если больше чем возникают ошибки передачи, приемник не может однозначно декодировать полученное слово в целом, поскольку может быть несколько возможных кодовых слов. Один из способов для получателя справиться с этой ситуацией - использовать расшифровка списка, в котором декодер выводит список всех кодовых слов в определенном радиусе.

Популярные обозначения

Обозначение описывает блочный код по алфавиту размера , с длиной блока , длина сообщения , и расстояние .Если блочный код является линейным блочным кодом, то квадратные скобки в обозначении используются для представления этого факта. Для двоичных кодов с , индекс иногда сбрасывается. коды максимального расстояния, расстояние всегда , но иногда точное расстояние неизвестно, нетривиально доказать или указать, или нет необходимости. В таких случаях -компонент может отсутствовать.

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

Примеры

Как упоминалось выше, существует огромное количество кодов с исправлением ошибок, которые на самом деле являются блочными кодами. Первым кодом с исправлением ошибок был Хэмминга (7,4) код, разработанный Ричард В. Хэмминг в 1950 году. Этот код преобразует сообщение, состоящее из 4 бит, в кодовое слово из 7 бит, добавляя 3 бита четности. Следовательно, этот код является блочным кодом. Оказывается, что это также линейный код, и что у него расстояние 3. В сокращенных обозначениях выше это означает, что код Хэмминга (7,4) является код.

Коды Рида – Соломона семья коды с и быть основная сила. Коды рангов семья коды с . Коды Адамара семья коды с и .

Свойства обнаружения и исправления ошибок

Кодовое слово можно рассматривать как точку в -размерное пространство и код это подмножество . Код имеет расстояние Значит это , другого кодового слова в Мяч Хэмминга сосредоточен на с радиусом , который определяется как набор -размерные слова, чьи Расстояние Хэмминга к не более чем . По аналогии, с (минимальным) расстоянием обладает следующими свойствами:

  • может обнаружить ошибки: потому что кодовое слово - единственное кодовое слово в шаре Хэмминга с центром в самом себе и радиусом , нет шаблонов ошибок или меньшее количество ошибок может изменить одно кодовое слово на другое. Когда приемник обнаруживает, что полученный вектор не является кодовым словом , ошибки обнаружены (но нет гарантии исправления).
  • может исправить ошибки. Потому что кодовое слово - единственное кодовое слово в шаре Хэмминга с центром в самом себе и радиусом , два шара Хэмминга с центрами в двух разных кодовых словах соответственно с обоими радиусами не пересекаются друг с другом. Следовательно, если рассматривать исправление ошибок как нахождение кодового слова, наиболее близкого к принятому слову , пока количество ошибок не более , в шаре Хэмминга есть только одно кодовое слово с центром в с радиусом , поэтому все ошибки можно исправить.
  • Для декодирования при наличии более ошибки, список-декодирование или же декодирование с максимальной вероятностью может быть использован.
  • может исправить стирания. К стирание это означает, что положение стертого символа известно. Исправление может быть достигнуто -проходящее декодирование: В прохождение стертой позиции заполняется символ и исправление ошибок. Должен быть один проход, что количество ошибок не более и поэтому стирания можно было исправить.

Нижняя и верхняя границы блочных кодов

Предел Хэмминга
Существуют теоретические пределы (например, предел Хэмминга), но другой вопрос заключается в том, какие коды могут быть фактически созданы. Это похоже на упаковка сфер в коробку во многих измерениях. Эта диаграмма показывает конструктивные коды, которые являются линейными и двоичными. В Икс ось показывает количество защищенных символов k, то у ось количество необходимых контрольных символов n – k. На графике показаны пределы для различных расстояний Хэмминга от 1 (без защиты) до 34. Точками отмечены точные коды:
  • светло-оранжевый горит Икс ось: банальные незащищенные коды
  • оранжевый на у ось: тривиальные повторяющиеся коды
  • темно-оранжевый на наборе данных d= 3: классические совершенные коды Хэмминга
  • темно-красный и крупнее: единственный идеальный двоичный код Голея

Семейство кодов

называется семейство кодов, куда является код с монотонным возрастанием .

Ставка семейства кодов C определяется как

Относительное расстояние семейства кодов C определяется как

Чтобы изучить взаимосвязь между и известен набор нижних и верхних границ блочных кодов.

Граница Хэмминга

Граница синглтона

Ограничение Синглтона заключается в том, что сумма скорости и относительного расстояния блочного кода не может быть намного больше 1:

.

Другими словами, каждый блочный код удовлетворяет неравенству .Коды Рида – Соломона являются нетривиальными примерами кодов, удовлетворяющих одноэлементной оценке равенства.

Плоткин граница

За , . Другими словами, .

В общем случае справедливы следующие оценки Плоткина для любых с расстоянием d:

  1. Если
  2. Если

Для любого q-арный код с расстоянием ,

Граница Гилберта – Варшамова

, куда , это q-арная энтропийная функция.

Джонсон связан

Определять .
Позволять - максимальное количество кодовых слов в шаре Хэмминга радиуса е для любого кода расстояния d.

Тогда у нас есть Джонсон Баунд : , если

Элиас – Бассалыго

Сферы и решетки

Коды блоков привязаны к проблема упаковки сфер которому на протяжении многих лет уделялось некоторое внимание. В двух измерениях это легко визуализировать. Возьмите связку монет на столе и сдвиньте их вместе. В результате получился шестиугольник, похожий на пчелиное гнездо. Но блочные коды полагаются на большее количество измерений, которые трудно визуализировать. Мощный Код Голея используется в дальнем космосе, используется 24 измерения. При использовании в качестве двоичного кода (что обычно бывает) размеры относятся к длине кодового слова, как определено выше.

Теория кодирования использует N-мерная сферическая модель. Например, сколько пенни можно упаковать в круг на столе или в 3-х измерениях, сколько шариков можно упаковать в глобус. Другие соображения относятся к выбору кода. Например, упаковка шестиугольника в прямоугольную коробку оставит пустые места по углам. По мере увеличения размеров процент пустого пространства становится меньше. Но при определенных размерах упаковка использует все пространство, и эти коды являются так называемыми совершенными кодами. Таких кодов очень мало.

Другое свойство - это количество соседей, которые может иметь одно кодовое слово.[1] Опять же, рассмотрим в качестве примера гроши. Сначала мы упаковываем пенни в прямоугольную сетку. У каждого пенни будет 4 ближайших соседа (и 4 на дальних углах). В шестиугольнике у каждого пенни будет 6 ближайших соседей. Соответственно, в трех и четырех измерениях максимальная упаковка определяется 12-гранный и 24-элементный с 12 и 24 соседями соответственно. Когда мы увеличиваем размеры, количество ближайших соседей увеличивается очень быстро. В общем, значение дается целующиеся числа.

В результате увеличивается количество способов, которыми шум заставляет приемник выбирать соседа (следовательно, возникает ошибка). Это фундаментальное ограничение блочных кодов, да и вообще всех кодов. Может быть сложнее вызвать ошибку для одного соседа, но количество соседей может быть достаточно большим, поэтому общая вероятность ошибки действительно страдает.[1]

Смотрите также

Рекомендации

  1. ^ а б c Кристиан Шлегель и Ланс Перес (2004). Решетки и турбо-кодирование. Wiley-IEEE. п. 73. ISBN 978-0-471-22755-7.

внешняя ссылка