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

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

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

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

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

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

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

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

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

${ Displaystyle C: Sigma ^ {k} to Sigma ^ {n}}$.

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

Алфавит Σ

Кодируемый поток данных моделируется как нить над некоторыми алфавит ${ displaystyle Sigma}$. Размер ${ displaystyle | Sigma |}$ алфавита часто записывается как ${ displaystyle q}$. Если ${ displaystyle q = 2}$, то код блока называется двоичный блочный код. Во многих приложениях полезно учитывать ${ displaystyle q}$ быть основная сила, и определить ${ displaystyle Sigma}$ с конечное поле ${ displaystyle mathbb {F} _ {q}}$.

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

Сообщения - это элементы ${ displaystyle m}$ из ${ displaystyle Sigma ^ {k}}$, то есть строки длины ${ displaystyle k}$. Следовательно, число ${ displaystyle k}$ называется длина сообщения или же измерение блочного кода.

Длина блока п

В длина блока ${ displaystyle n}$ кода блока - это количество символов в блоке. Следовательно, элементы ${ displaystyle c}$ из ${ Displaystyle Sigma ^ {п}}$ строки длины ${ displaystyle n}$ и соответствуют блокам, которые могут быть приняты получателем. Поэтому их еще называют принятыми словами. ${ Displaystyle с = С (м)}$ для какого-то сообщения ${ displaystyle m}$, тогда ${ displaystyle c}$ называется кодовым словом ${ displaystyle m}$.

Оценка р

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

${ Displaystyle R = к / п}$.

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

Расстояние d

В расстояние или же минимальное расстояние d блочного кода - это минимальное количество позиций, в которых различаются любые два различных кодовых слова, а относительное расстояние ${ displaystyle delta}$ это дробь ${ displaystyle d / n}$. Формально для полученных слов ${ displaystyle c_ {1}, c_ {2} in Sigma ^ {n}}$, позволять ${ displaystyle Delta (c_ {1}, c_ {2})}$ обозначить Расстояние Хэмминга между ${ displaystyle c_ {1}}$ и ${ displaystyle c_ {2}}$, то есть количество позиций, в которых ${ displaystyle c_ {1}}$ и ${ displaystyle c_ {2}}$ отличаются. Тогда минимальное расстояние ${ displaystyle d}$ кода ${ displaystyle C}$ определяется как

${ displaystyle d: = min _ {m_ {1}, m_ {2} in Sigma ^ {k} на вершине m_ {1} neq m_ {2}} Delta [C (m_ {1}) , C (m_ {2})]}$.

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

${ displaystyle min _ {m_ {1}, m_ {2} in Sigma ^ {k} на вершине m_ {1} neq m_ {2}} Delta [C (m_ {1}), C ( m_ {2})] = min _ {m_ {1}, m_ {2} in Sigma ^ {k} поверх m_ {1} neq m_ {2}} Delta [ mathbf {0}, C (m_ {1}) + C (m_ {2})] = min _ {m in Sigma ^ {k} atop m neq mathbf {0}} w [C (m)] = w_ { min}}$.

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

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

Обозначение ${ displaystyle (п, к, d) _ {q}}$ описывает блочный код по алфавиту ${ displaystyle Sigma}$ размера ${ displaystyle q}$, с длиной блока ${ displaystyle n}$, длина сообщения ${ displaystyle k}$, и расстояние ${ displaystyle d}$.Если блочный код является линейным блочным кодом, то квадратные скобки в обозначении ${ displaystyle [п, к, d] _ {q}}$ используются для представления этого факта. Для двоичных кодов с ${ displaystyle q = 2}$, индекс иногда сбрасывается. коды максимального расстояния, расстояние всегда ${ Displaystyle д = п-к + 1}$, но иногда точное расстояние неизвестно, нетривиально доказать или указать, или нет необходимости. В таких случаях ${ displaystyle d}$-компонент может отсутствовать.

Иногда, особенно для неблочных кодов, обозначение ${ displaystyle (п, M, d) _ {q}}$ используется для кодов, содержащих ${ displaystyle M}$ кодовые слова длины ${ displaystyle n}$. Для блочных кодов с сообщениями длины ${ displaystyle k}$ над алфавитом размера ${ displaystyle q}$, это число будет ${ Displaystyle М = д ^ {к}}$.

Примеры

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

Коды Рида – Соломона семья ${ displaystyle [п, к, d] _ {q}}$ коды с ${ Displaystyle д = п-к + 1}$ и ${ displaystyle q}$ быть основная сила. Коды рангов семья ${ displaystyle [п, к, d] _ {q}}$ коды с ${ Displaystyle д Leq п-к + 1}$. Коды Адамара семья ${ displaystyle [п, к, d] _ {2}}$ коды с ${ Displaystyle п = 2 ^ {к-1}}$ и ${ displaystyle d = 2 ^ {k-2}}$.

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

Кодовое слово ${ displaystyle c in Sigma ^ {n}}$можно рассматривать как точку в ${ displaystyle n}$-размерное пространство ${ Displaystyle Sigma ^ {п}}$ и код ${ displaystyle { mathcal {C}}}$ это подмножество ${ Displaystyle Sigma ^ {п}}$. Код ${ displaystyle { mathcal {C}}}$ имеет расстояние ${ displaystyle d}$ Значит это ${ displaystyle forall c in { mathcal {C}}}$, другого кодового слова в Мяч Хэмминга сосредоточен на ${ displaystyle c}$ с радиусом ${ displaystyle d-1}$, который определяется как набор ${ displaystyle n}$-размерные слова, чьи Расстояние Хэмминга к ${ displaystyle c}$ не более чем ${ displaystyle d-1}$. По аналогии, ${ displaystyle { mathcal {C}}}$ с (минимальным) расстоянием ${ displaystyle d}$ обладает следующими свойствами:

• ${ displaystyle { mathcal {C}}}$ может обнаружить ${ displaystyle d-1}$ ошибки: потому что кодовое слово ${ displaystyle c}$ - единственное кодовое слово в шаре Хэмминга с центром в самом себе и радиусом ${ displaystyle d-1}$, нет шаблонов ошибок ${ displaystyle d-1}$ или меньшее количество ошибок может изменить одно кодовое слово на другое. Когда приемник обнаруживает, что полученный вектор не является кодовым словом ${ displaystyle { mathcal {C}}}$, ошибки обнаружены (но нет гарантии исправления).
• ${ displaystyle { mathcal {C}}}$ может исправить ${ displaystyle textstyle left lfloor {{d-1} over 2} right rfloor}$ ошибки. Потому что кодовое слово ${ displaystyle c}$ - единственное кодовое слово в шаре Хэмминга с центром в самом себе и радиусом ${ displaystyle d-1}$, два шара Хэмминга с центрами в двух разных кодовых словах соответственно с обоими радиусами ${ displaystyle textstyle left lfloor {{d-1} over 2} right rfloor}$ не пересекаются друг с другом. Следовательно, если рассматривать исправление ошибок как нахождение кодового слова, наиболее близкого к принятому слову ${ displaystyle y}$, пока количество ошибок не более ${ displaystyle textstyle left lfloor {{d-1} over 2} right rfloor}$, в шаре Хэмминга есть только одно кодовое слово с центром в ${ displaystyle y}$ с радиусом ${ displaystyle textstyle left lfloor {{d-1} over 2} right rfloor}$, поэтому все ошибки можно исправить.
• Для декодирования при наличии более ${ displaystyle (d-1) / 2}$ ошибки, список-декодирование или же декодирование с максимальной вероятностью может быть использован.
• ${ displaystyle { mathcal {C}}}$ может исправить ${ displaystyle d-1}$ стирания. К стирание это означает, что положение стертого символа известно. Исправление может быть достигнуто ${ displaystyle q}$-проходящее декодирование: В ${ displaystyle i ^ {th}}$ прохождение стертой позиции заполняется ${ displaystyle i ^ {th}}$ символ и исправление ошибок. Должен быть один проход, что количество ошибок не более ${ displaystyle textstyle left lfloor {{d-1} over 2} right rfloor}$ и поэтому стирания можно было исправить.

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

Предел Хэмминга

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

• светло-оранжевый горит Икс ось: банальные незащищенные коды
• оранжевый на у ось: тривиальные повторяющиеся коды
• темно-оранжевый на наборе данных d= 3: классические совершенные коды Хэмминга
• темно-красный и крупнее: единственный идеальный двоичный код Голея

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

${ Displaystyle C = {C_ {я} } _ {я geq 1}}$ называется семейство кодов, куда ${ displaystyle C_ {i}}$ является ${ Displaystyle (п_ {я}, к_ {я}, д_ {я}) _ {д}}$ код с монотонным возрастанием ${ displaystyle n_ {i}}$.

Ставка семейства кодов C определяется как ${ Displaystyle R (C) = lim _ {я к infty} {k_ {i} over n_ {i}}}$

Относительное расстояние семейства кодов C определяется как ${ displaystyle delta (C) = lim _ {i to infty} {d_ {i} over n_ {i}}}$

Чтобы изучить взаимосвязь между ${ Displaystyle R (C)}$ и ${ displaystyle delta (C)}$известен набор нижних и верхних границ блочных кодов.

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

${ Displaystyle R Leq 1- {1 над n} CDOT log _ {q} CDOT left [ sum _ {я = 0} ^ { left lfloor {{ delta cdot n-1 } over 2} right rfloor} { binom {n} {i}} (q-1) ^ {i} right]}$

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

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

${ displaystyle R + delta leq 1 + { frac {1} {n}}}$.

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

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

За ${ displaystyle q = 2}$, ${ Displaystyle R + 2 дельта leq 1}$. Другими словами, ${ Displaystyle к + 2д leq п}$.

В общем случае справедливы следующие оценки Плоткина для любых ${ Displaystyle С substeq mathbb {F} _ {q} ^ {п}}$ с расстоянием d:

1. Если ${ displaystyle d = left (1- {1 над q} right) n, | C | leq 2qn}$
2. Если ${ displaystyle d> left (1- {1 над q} right) n, | C | leq {qd over {qd- left (q-1 right) n}}}$

Для любого q-арный код с расстоянием ${ displaystyle delta}$, ${ Displaystyle R Leq 1- влево ({д над {q-1}} вправо) дельта + о влево (1 вправо)}$

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

${ Displaystyle R GEQ 1-H_ {q} влево ( дельта вправо) - epsilon}$, куда ${ displaystyle 0 leq delta leq 1- {1 над q}, 0 leq epsilon leq 1-H_ {q} left ( delta right)}$,${ displaystyle H_ {q} left (x right) ~ { overset { underset { mathrm {def}} {}} {=}} ~ -x cdot log _ {q} {x over {q-1}} - left (1-x right) cdot log _ {q} { left (1-x right)}}$ это q-арная энтропийная функция.

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

Определять ${ Displaystyle J_ {q} left ( delta right) ~ { overset { underset { mathrm {def}} {}} {=}} ~ left (1- {1 over q} right ) left (1 - { sqrt {1- {q delta over {q-1}}}} right)}$.
Позволять ${ displaystyle J_ {q} left (n, d, e right)}$ - максимальное количество кодовых слов в шаре Хэмминга радиуса е для любого кода ${ Displaystyle С substeq mathbb {F} _ {q} ^ {п}}$ расстояния d.

Тогда у нас есть Джонсон Баунд : ${ displaystyle J_ {q} left (n, d, e right) leq qnd}$, если ${ displaystyle {e over n} leq {{q-1} over q} left ({1 - { sqrt {1- {q over {q-1}}} cdot {d over n) }}}} , right) = J_ {q} left ({d over n} right)}$

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

${ Displaystyle R = { log _ {q} {| C |} над n} leq 1-H_ {q} left (J_ {q} left ( delta right) right) + о влево (1 вправо)}$

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

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

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

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

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

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

• Емкость канала
• Теорема Шеннона – Хартли.
• Шумный канал
• Расшифровка списка^[1]
• Упаковка сфер

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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Блокировать код» – Новости · газеты · книги · ученый · JSTOR (Сентябрь 2008 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

• J.H. ван Линт (1992). Введение в теорию кодирования. GTM. 86 (2-е изд.). Springer-Verlag. п.31. ISBN 3-540-54894-7.
• Ф.Дж. МакУильямс; N.J.A. Sloane (1977). Теория кодов, исправляющих ошибки. Северная Голландия. п.35. ISBN 0-444-85193-3.
• У. Хаффман; В.Плесс (2003). Основы кодов с исправлением ошибок. Издательство Кембриджского университета. ISBN 978-0-521-78280-7.
• С. Линь; Д. Дж. Младший Костелло (1983). Кодирование с контролем ошибок: основы и приложения. Прентис-Холл. ISBN 0-13-283796-X.

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

• Чаран Лэнгтон (2001) Концепции кодирования и блочное кодирование