Цитата(Gold777 @ Nov 2 2012, 17:52)

Можете объяснить, что значит плотная упаковка кода и почему чем больше Dmin, тем больше ошибок можно исправить за пределами исправляющей способности кода?
Любой код можно представить в виде точек в n - мерном пространстве Хемминга.
У каждого кода есть минимальное расстояние. Это значит, что если провести в пространстве Х.
сферу радиуса Dmin/2 вокруг каждого кодового слова, то получившиеся сферы не будут пересекаться.
И наоборот, если провести сферы радиуса хоть на одну единицу больше - то сферы начнут пересекаться.
Рассмотри шары радиуса Dmin/2, т.е. пересечений еще нет.
Вопрос: какая доля всего пространства Хемминга векторов длины n "вычерпана" этими шарами?
Ответ зависит от кода. Для кодов Хэмминга (это те, которые исправляют одну ошибку),
эти шары вычерпывают ровно ВСЕ пространство. Известно, что "почти все" пространство
вычерпывают примитивные коды БЧХ, исправляющие две ошибки. Эти коды относят к классу плотно упакованных.
Чем больше радиус шаров, тем больше пространства остается "в промежутках" между шарами.
Конечно, это не абсолютное правило (вспомним код Голея), но общая тенденция именно такая.
Чем дальше кодовые параметры от границы Хемминга, тем хуже упакован код.
Удобнее рассматривать смежные классы кода, чтобы понять упакованность кода.
В лидерах смежных классов, как известно, находятся те вектора ошибок, которые может
исправить код (при оптимальном декодировании, например полным перебором).
Так вот, у совершенных кодов (например, код Хемминга), все лидеры имеет вес 1, причем это все вектора веса 1.
Для квазисовершеннх кодов в лидерах есть все вектора веса до Dmin/2, и некоторые вектора веса Dmin/2 +1.
Это, например, упомянутые выше квазисовершенные БЧХ коды с Dmin =5.
Чем хуже упаковано шарами Хеммингово пространство, тем больше тяжелых лидеров существует в стандартной
расстановке для данного кода.
Я когда-то делал моделирование для длинных БЧХ кодов (16тыс бит.)
Для кодов с Dmin = 7..13 довольно часто встречались случайные вектора ошибок веса n/2,
которые переводили слово в другую сферу. Т.е. происходила неисправимая ошибка, которая приводила к неправильному декодированию в другое кодовое слово.
Это значит, что шары для этих кодов более-менее плотно заполняли пространство.
А вот для кодов с Dmin >30 даже на сотнях тысяч опытов не удавалось попасть в кодовую сферу.
Т.е. в качестве вектора ошибки генерировался случайный вектор веса n/2, далее выполнялось
декодирование по БМ, но в результате получался отказ от декодирования,
т.е. от полученного вектора на расстоянии Dmin/2 не находилось ни одного кодового слова.
Это означает, что доля пространства, высекаемая кодовыми шарами радиуса Dmin/2 была почти нулевой для больших Dmin.
Так что даже случайно тыкая пальцем в произвольный вектор в пространстве Хемминга,
мы почти с нулевой вероятностью попадали в окрестность хоть какого-нибудь кодового слова.
Это и означает, что данные коды были весьма далеки от плотной упаковки.
А вообще задачи максимально плотно упаковки разных пространств
шарами или другими объектами - это отдельная наука (и не только кодировочная), на эту тему написана куча книжек.
Поищите в и-нете.