5. Резюме

Для удобства ссылок мы воспроизведем здесь основные результаты этой главы.

Кодирование. Двоичная последовательность х длины преобразуется в двоичную последовательность длины пр которая посылается по двоичному симметричному каналу. Двоичная последовательность у длины возникает на выходе канала. Совокупность 5 всех последовательностей имеет элементов. Преобразование таково, что элементы 5 могут быть представлены как дерево (см. рис. 10). Мы называем древовидным кодом. Этот код обладает тем важным свойством, что если произвести усечение его при длине то остаток будет содержать примерно последовательностей.

Декодирование. Декодирующее устройство хранит в своей памяти (или способно вычислить) матрицу

связанную с возрастающей последовательностью критериев так, что строка в матрице соответствует критерию Для того чтобы декодировать (первый символ употребляется следующий алгоритм.

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

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

3. Если ни одна из последовательностей 5 не сохраняется вплоть до длины то декодирующее устройство начинает сначала, используя теперь критерий Всякий раз, когда выясняется, что все

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

Объем вычислений. Мы определяем как подмножество, состоящее из всех элементов которые не согласуются с истинным значением Для надлежащим образом выбранной матрицы средний объем вычислений, требуемый для того, чтобы перебрать ограничен сверху величиной, пропорциональной Этот результат верен при Величина зависит от переходных вероятностей канала; эта зависимость показана на рис. 11.

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