1.5. Теорема кодирования
Теория кодирования насчитывает уже более чем двадцатилетнюю историю и сейчас можно указать очень много примеров ее применения. Ученые и инженеры, которые работали в области теории кодирования на начальном этапе ее развития, считали основной своей задачей разработку практически приемлемых методов реализации теоремы кодирования Шеннона [9]. Согласно этой теореме, для широкого класса каналов при передаче информации со скоростью, меньшей пропускной способности канала, путем увеличения длины кода можно достичь сколь угодно малой вероятности ошибки при передаче. Известно, что в дискретном канале без памяти (предполагается, что шумы в канале являются случайными) вероятность ошибки при передаче 
для кода длины 
оценивается следующим образом:
где 
некоторые функции скорости передачи 
и переходных вероятностей канала, 
функции, стремящиеся к нулю с ростом 
константа. В области скоростей 
близких к пропускной способности канала, функции 
совпадают, т.е. 
Как видно из неравенств (1.14), если значения функций 
положительны, то, выбрав длину кода 
достаточно большой, вероятность ошибки можно сделать сколь угодно малой.
Верхняя граница вероятности ошибки в (1.14) была получена Шенноном путем определения средней вероятности ошибки в ансамбле кодов. Этот метод сравнительно сложен. Галлагер [10,20] предложил более простой метод получения этой границы. Метод Галлагера оказался применимым не только для упрощения доказательства теоремы кодирования, он, в частности, широко используется при изучении поведения алгоритмов последовательного декодирования.
Функция 
входящая в нижнюю границу для вероятности ошибки в (1.14), была найдена Шенноном, Галлагером и Берлекэмпом методом, в основном аналогичным методу нахождения функции 
[21].
На основании вышеизложенного можно считать, что рассмотрение здесь метода Галлагера и других вопросов, связанных с верхней и нижней границами (1.14) для вероятности ошибки, будет полезным для понимания методов, которые оказали существенное влияние на развитие теории кодирования. С другой стороны, этот материал потребуется нам в дальнейшем.
