Блочный код

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

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

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


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

Блочный  — , ирующий последовательности наборов символов из алфавита S в овые слова, преобразуя каждый символ из S отдельно. Пусть  — последовательность натуральных чисел, каждое меньше |S|. Если и некоторое слово W из алфавита S записано как , тогда овым словом, соответствующим W, а именно, C(W), будет: .

[n, d][ | ]

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

Информационные нормы[ | ]

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

.

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

.

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

Блочные ы связаны с проблемой сферической упаковки, которая привлекла к себе внимания в последние годы. В двух измерениях её легко визуализировать, взяв горсть одинаковых монет и выстроив их на столе в виде шестиугольника, как в пчелиных сотах. Однако в больших измерениях блочные ы не удаётся визуализировать так же легко. Сильный Голея, используемый в коммуникациях открытого космоса, использует 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.