Код блокировки - Block code

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

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

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

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

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

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

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

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

${\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 ^{n}}$ строки длины ${\displaystyle n}$ и соответствуют блокам, которые могут быть приняты получателем. Поэтому их еще называют принятыми словами. ${\displaystyle c=C(m)}$ для какого-то сообщения ${\displaystyle m}$, тогда ${\displaystyle c}$ называется кодовым словом ${\displaystyle m}$.

Оценка р

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

${\displaystyle R=k/n}$.

Большая скорость означает, что количество фактического сообщения на переданный блок велико. В этом смысле скорость измеряет скорость передачи и количество ${\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} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$.

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

${\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop 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 (n,k,d)_{q}}$ описывает блочный код по алфавиту ${\displaystyle \Sigma }$ размера ${\displaystyle q}$, с длиной блока ${\displaystyle n}$, длина сообщения ${\displaystyle k}$, и расстояние ${\displaystyle d}$.Если блочный код является линейным блочным кодом, то квадратные скобки в обозначении ${\displaystyle [n,k,d]_{q}}$ используются для представления этого факта. Для двоичных кодов с ${\displaystyle q=2}$, индекс иногда сбрасывается. коды максимального расстояния, расстояние всегда ${\displaystyle d=n-k+1}$, но иногда точное расстояние неизвестно, нетривиально доказать или указать, или нет необходимости. В таких случаях ${\displaystyle d}$-компонент может отсутствовать.

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

Примеры

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

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

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

Кодовое слово ${\displaystyle c\in \Sigma ^{n}}$можно рассматривать как точку в ${\displaystyle n}$-размерное пространство ${\displaystyle \Sigma ^{n}}$ и код ${\displaystyle {\mathcal {C}}}$ это подмножество ${\displaystyle \Sigma ^{n}}$. Код ${\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_{i}\}_{i\geq 1}}$ называется семейство кодов, куда ${\displaystyle C_{i}}$ является ${\displaystyle (n_{i},k_{i},d_{i})_{q}}$ код с монотонным возрастанием ${\displaystyle n_{i}}$.

Ставка семейства кодов C определяется как ${\displaystyle R(C)=\lim _{i\to \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 \over n}\cdot \log _{q}\cdot \left[\sum _{i=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 k+d\leq n+1}$.Коды Рида – Соломона являются нетривиальными примерами кодов, удовлетворяющих одноэлементной оценке равенства.

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

Основная статья: Плоткин граница

За ${\displaystyle q=2}$, ${\displaystyle R+2\delta \leq 1}$. Другими словами, ${\displaystyle k+2d\leq n}$.

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

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

Для любого q-арный код с расстоянием ${\displaystyle \delta }$, ${\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}$

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

Основная статья: Граница Гилберта – Варшамова

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$, куда ${\displaystyle 0\leq \delta \leq 1-{1 \over 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 C\subseteq \mathbb {F} _{q}^{n}}$ расстояния 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|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}$

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

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

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

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

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

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

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

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

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

• 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) Концепции кодирования и блочное кодирование