Границы кодов, исправляющих ошибки

В теории кодирования доказывается ряд теорем о верхних и нижних гра­ницах кодов, которые указывают на возможности кодов контролировать ошибки. Эти возможности определяются структурой кодового пространства. Очевидно, что при увеличении кодового расстояния d кратность контролируемых ошибок t возрастает за счет увеличения числа избыточных символов r, а это при­водит к уменьшению числа информационных символов k и, следовательно, множе- ства кодовых слов M=q^k.

Между параметрами (п, d, М) существует взаимосвязь,

определяющая оп­тимальный выбор кодов, решаемый, как

правило, тремя способами.

9) При заданных М и п максимизируется d. Подобным образом построенные коды получили название максиминных.

10) При заданных M и d минимизируется длина сообщения п, т.е. отыскива­ются коды с минимальной избыточностью.

11) При заданных п и d находят коды с максимальным числом кодовых слов М. Такие коды называют максимальными.

Рис. 6.13. Границы кодов, контролирующих ошибки:

1 - нижняя граница Варшамова-Гильберта; 2 - верхняя граница Хэмминга; 3 - верхняя граница для кодов, исправляющих дефекты

Данные три процедуры по нахождению кодов не приводят к одному и тому же решению. К настоящему времени ни одна из задач полностью не решена, однако существует большое число оценок (границ) качества кодов. На практике наиболее широко используют верхние границы Хэмминга и Плоткина, нижнюю границу Варшамова-Гильберта. На практике считается, что код является достаточно хорошим, если его параметры лежат выше границ Варшамова-Гильберта и ниже верхней границы Хэмминга (в заштрихованной области рис. 6.13).