Сложность построения кодов, обладающих заданными корректирующими свойствами

Исследуется, с какой сложностью можно строить коды, удовлетворяющие известным асимптотическим границам для вероятности ошибки. Рассмотрены способы неслучайного выбора двоичного линейного кода, лежащего на границе Галлагера, и построения каскадного кода, лежащего на границе Форни. Показано, что при любой длине кода $n$ сложность построения линейного кода ограничена сверху экспонентой, а каскадного кода – степенной функцией от $n$.