Блочный лук
- 1 year ago
- 0
- 0
Блочный код — в информатике тип канального кодирования. Он увеличивает избыточность сообщения так, чтобы в приёмнике можно было расшифровать его с минимальной (теоретически нулевой) погрешностью, при условии, что скорость передачи информации (количество передаваемой информации в битах в секунду) не превысила бы .
Главная характеристика блочного кода состоит в том, что это — канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана , и в отличие от таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование)). Обычно система блочного кодирования получает на входе k -значное кодовое слово W , и преобразовывает его в n -значное кодовое слово C(W) . Это кодовое слово и называется блоком.
Блочное кодирование было главным типом кодирования, используемого в ранних системах мобильной коммуникации.
Блочный код — код, кодирующий последовательности наборов символов из алфавита S в кодовые слова, преобразуя каждый символ из S отдельно. Пусть — последовательность натуральных чисел , каждое меньше |S| . Если и некоторое слово W из алфавита S записано как , тогда кодовым словом, соответствующим W , а именно, C(W) , будет: .
Компромисс между эффективностью (большей скоростью передачи информации) и способностями исправления может также быть виден при попытке задать фиксированную длину ключевого слова, и фиксированную возможность исправления (представленную расстоянием Хемминга d ) и максимизируют общее количество ключевых слов. [n, d] — максимальное число ключевых слов для данной длины ключевого слова n и расстояния Хемминга d .
Когда C — двойной блочный код, состоящий из А ключевых слов длиной n бит, тогда информационная норма C определяется как:
В случае, когда первые k бит ключевого слова — независимые информационные биты, то информационная норма будет иметь вид:
Блочные коды связаны с проблемой сферической упаковки, которая привлекла к себе внимания в последние годы. В двух измерениях её легко визуализировать, взяв горсть одинаковых монет и выстроив их на столе в виде шестиугольника, как в пчелиных сотах. Однако в больших измерениях блочные коды не удаётся визуализировать так же легко. Сильный код Голея, используемый в коммуникациях открытого космоса, использует 24 измерения. Если используется двоичный код (как это обычно и делается), измерения обращаются к длине ключевого слова, как определено выше.
Теория кодирования использует модель N-мерной сферы. Например, сколько монет может быть уложено в круг на поверхности стола или в 3 измерениях, сколько мрамора может быть помещено в земной шар. Другие рассмотрения входят в выбор кода. Например, шестиугольник, помещённый в ограниченную прямоугольную коробку, оставит пустое место в углах. Поскольку измерения увеличиваются, процент от пустого места становится меньшим. Но в определённых измерениях заполняется все место и эти коды — так называемые совершенные коды. Но их очень мало.
Другим пунктом, который часто пропускается, является число соседей, которых может иметь единственное ключевое слово. Снова будем использовать монеты в качестве примера. Сначала мы укладываем их в прямоугольной сетке. У каждой монеты будет 4 близких соседа (и 4 в наиболее удалённых углах). В шестиугольнике у каждой монеты будет 6 близких соседей. Когда мы увеличиваем количество измерений, число близких соседей растёт очень быстро.
Результат — также рост числа путей, когда шум вынуждал бы получателя выбрать соседа; следовательно — ошибка. Это — фундаментальное ограничение блочных кодов, и действительно всех кодов. Может быть, единственному соседу тяжелее вызвать ошибку, но число соседей может быть достаточно большим, таким образом полная ошибочная вероятность фактически возможна.