Блочный код

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

Главная характеристика блочного кода состоит в том, что это — канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана, и в отличие от таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование)). Обычно система блочного кодирования получает на входе k-значное кодовое слово W, и преобразовывает его в n-значное кодовое слово C(W). Это кодовое слово и называется блоком.

Блочное кодирование было главным типом кодирования, используемого в ранних системах мобильной коммуникации.

Формальное определение

Блочный код — код, кодирующий последовательности наборов символов из алфавита S в кодовые слова, преобразуя каждый символ из S отдельно. Пусть $(k_{1},k_{2},\ldots ,k_{m})$ — последовательность натуральных чисел, каждое меньше |S|. Если $S=\{s_{1},s_{2},\ldots ,s_{n}\}$ и слово W из алфавита S записано как $W=s_{k_{1}}s_{k_{2}}\ldots s_{k_{m}}$, тогда кодовым словом, соответствующим W, а именно, C(W), будет: $C(W)=C(s_{k_{1}})C(s_{k_{2}})\ldots C(s_{k_{m}})$ .

[n, d]

Компромисс между эффективностью (большей скоростью передачи информации) и способностями исправления может также быть виден при попытке задать фиксированную длину ключевого слова, и фиксированную возможность исправления (представленную расстоянием Хемминга d) и максимизируют общее количество ключевых слов. [n, d] — максимальное число ключевых слов для данной длины ключевого слова n и расстояния Хемминга d.

Информационные нормы

Когда C — двойной блочный код, состоящий из А ключевых слов длиной n бит, тогда информационная норма C определяется как:

${\frac {\log _{2}(A)}{n}}$.

В случае, когда первые k бит ключевого слова — независимые информационные биты, то информационная норма будет иметь вид:

${\frac {\log _{2}(2^{k})}{n}}={\frac {k}{n}}$.

Сферические упаковки и решётки

Блочные коды связаны с проблемой сферической упаковки, которая привлекла к себе внимания в последние годы. В двух измерениях её легко визуализировать, взяв горсть одинаковых монет и выстроив их на столе в виде шестиугольника, как в пчелиных сотах. Однако в больших измерениях блочные коды не удаётся визуализировать так же легко. Сильный код Голея, используемый в коммуникациях открытого космоса, использует 24 измерения. Если используется двоичный код (как это обычно и делается), измерения обращаются к длине ключевого слова, как определено выше.

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

Другим пунктом, который часто пропускается, является число соседей, которых может иметь единственное ключевое слово. Снова будем использовать монеты в качестве примера. Сначала мы укладываем их в прямоугольной сетке. У каждой монеты будет 4 близких соседа (и 4 в наиболее удалённых углах). В шестиугольнике у каждой монеты будет 6 близких соседей. Когда мы увеличиваем количество измерений, число близких соседей растёт очень быстро.

Результат — также рост числа путей, когда шум вынуждал бы получателя выбрать соседа; следовательно — ошибка. Это — фундаментальное ограничение блочных кодов, и действительно всех кодов. Может быть, единственному соседу тяжелее вызвать ошибку, но число соседей может быть достаточно большим, таким образом полная ошибочная вероятность фактически возможна.

Литература

• J. H van Lint (1992). Введение в Теорию Кодирования. GTM. 86 (2-е издание). Springer-Verlag. p. 31. ISBN 3-540-54894-7.
• F. J. MacWilliams; N.J.A. Sloane (1977). Теория кодов, исправляющих ошибки. Северная Голландия. p. 35. ISBN 0-444-85193-3.
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Изд. "Мир", 1976.