Границы сложности декодирования линейных блоковых кодов с помощью решеток

Показано, что синдромная решетка [1, 2] минимальна. Приведено простое доказательство нижней границы числа узлов кодовой решетки. Получены границы экспоненты сложности мягкого декодирования максимального правдоподобия по решетке.
Для кодов, удовлетворяющих границе Варшамова. показано, что хотя почти все коды лежат на верхней границе сложности, блоковые коды, полученные усечением сверточных, имеют экспоненциально меньшую сложность декодирования по решетке. Эта сложность является минимально возможной при справедливости гипотезы о точности границы Варшамова для двоичных кодов.