Блочный код

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

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

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

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

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

log 2 ⁡ ( A ) n {displaystyle {frac {log _{2}(A)}{n}}} .

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

log 2 ⁡ ( 2 k ) n = k n {displaystyle {frac {log _{2}(2^{k})}{n}}={frac {k}{n}}} .

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

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

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

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

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