Код блока

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

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

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

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

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

Длина блока n

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

Ставка R

Скорость блочного кода определяется как отношение длины его сообщения к длине блока :

${\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 }$

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

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

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

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

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

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

• Пропускная способность канала
• Теорема Шеннона – Хартли
• Шумный канал
• Декодирование списка ^[1]
• Сферическая упаковка

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

1. Кристиан Шлегель и Лэнс Перес (2004). Треллис и турбокодирование. Вайли-IEEE. п. 73. ИСБН 978-0-471-22755-7.

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

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

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