Блок-код

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

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

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

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

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

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

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

Формально блочный код представляет собой инъективное отображение.

C:\Sigma ^{k}\to \Sigma ^{n}

.

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

Алфавит С

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

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

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

Длина блока n

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

Ставка R

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

R=k/n

.

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

Расстояние d

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

d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]

.

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

\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$ позволяет приемнику обнаруживать до $d-1$ ошибки передачи с момента изменения $d-1$ позиции кодового слова никогда не могут случайно привести к другому кодовому слову. Кроме того, если не более $(d-1)/2$ возникают ошибки передачи, приемник может однозначно декодировать полученное слово в кодовое слово. Это связано с тем, что каждое принятое слово имеет не более одного кодового слова на расстоянии. $(d-1)/2$ . Если более чем $(d-1)/2$ возникают ошибки передачи, приемник не может однозначно декодировать полученное слово, поскольку возможных кодовых слов может быть несколько. Одним из способов справиться с этой ситуацией получателя является использование декодирования списка , при котором декодер выводит список всех кодовых слов в определенном радиусе.

Примеры

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

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

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

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

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

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

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

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

$C=\{C_{i}\}_{i\geq 1}$ называется семейством кодов , где $C_{i}$ это $(n_{i},k_{i},d_{i})_{q}$ код с монотонным возрастанием $n_{i}$ .

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

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

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

Хэмминг связан

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:

R+\delta \leq 1+{\frac {1}{n}}

.

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

Плоткин связан

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

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

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

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

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

$R\geq 1-H_{q}\left(\delta \right)-\epsilon$ , где $0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)$ , $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$ -арная функция энтропии.

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

Определять $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)$ .
Позволять $J_{q}\left(n,d,e\right)$ — максимальное количество кодовых слов в шаре Хэмминга радиуса $e$ для любого кода. $C\subseteq \mathbb {F} _{q}^{n}$ расстояния $d$ .

Тогда у нас есть граница Джонсона : $J_{q}\left(n,d,e\right)\leq qnd$ , если ${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)$

Дорога Элиаса – Бассалиго

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]

См. также

Ссылки

^ Jump up to: ^а ^б ^с Кристиан Шлегель и Лэнс Перес (2004). Треллис и турбокодирование . Wiley-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) Концепции кодирования и блочное кодирование

[schlegel-1] Jump up to: ^а ^б ^с Кристиан Шлегель и Лэнс Перес (2004). Треллис и турбокодирование . Wiley-IEEE. п. 73. ИСБН 978-0-471-22755-7 .

[1]