Блокировать код

Семейство кодов с исправлением ошибок, которые кодируют данные в блоках

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

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

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

Термин блочный код может также относиться к любому коду с исправлением ошибок, который действует на блок бит входных данных для создания бит выходных данных . Следовательно, блочный кодер является устройством без памяти . Согласно этому определению, такие коды, как турбокоды , завершенные сверточные коды и другие итеративно декодируемые коды (турбоподобные коды), также будут считаться блочными кодами. Незавершенный сверточный кодер будет примером неблочного (некадрированного) кода, который имеет память и вместо этого классифицируется как древовидный код . ${\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}}$

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

Сообщения являются элементами , то есть строками длины . Поэтому число называется длиной сообщения или размерностью блочного кода. ${\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 блочного кода — это минимальное число позиций, в которых различаются любые два различных кодовых слова, а относительное расстояние — это дробь . Формально, для полученных слов , пусть обозначает расстояние Хэмминга между и , то есть число позиций, в которых различаются и . Тогда минимальное расстояние кода определяется как ${\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 }$

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

Предел Хэмминга ^{[ требуется разъяснение ]}

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

• светло-оранжевый на оси x : тривиальные незащищенные коды
• оранжевый на оси Y : тривиальные повторные коды
• темно-оранжевый на наборе данных 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}$

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

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 }$, где , — q -ичная функция энтропии. ${\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)}}$

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

Определим . Пусть будет максимальным числом кодовых слов в шаре Хэмминга радиуса e для любого кода с расстоянием d . ${\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}}$

Тогда у нас есть граница Джонсона  : , если ${\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.

• JH van Lint (1992). Введение в теорию кодирования. GTM . Т. 86 (2-е изд.). Springer-Verlag. стр. 31. ISBN 3-540-54894-7.
• FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. стр. 35. ISBN 0-444-85193-3.
• W. Huffman; V. Pless (2003). Основы кодов исправления ошибок . Cambridge University Press. ISBN 978-0-521-78280-7.
• S. Lin; DJ Jr. Costello (1983). Кодирование с контролем ошибок: основы и приложения . Prentice-Hall. ISBN 0-13-283796-X.

Внешние ссылки

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