4.5. Обсуждение границ

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

Коды Хэмминга и в случае больших скоростей передачи эквивалентные коды Рида — Маллера и коды Боуза — Чоудхури, рассматриваемые в следующих главах, лежат на границе Хэмминга и являются оптимальными. Коды Макдональда и коды Рида — Маллера и Боуза — Чоудхури для малых скоростей передачи лежат на границе Плоткина. Следовательно, все эти коды имеют наибольшее возможное минимальное расстояние. Тем не менее при больших значениях скорости передачи для всех этих кодов стремятся либо к нулю, либо к единице. В области средних скоростей передачи как для кодов Рида — Маллера, так и для кодов Боуза — Чоудхури, насколько можно судить по наилучшим известным оценкам, при любой фиксированной

ненулевой скорости передачи отношение стремится к 0, когда неограниченно возрастает. Коды Боуза — Чоудхури, однако, все еще лежат приблизительно на границе Варшамова-Гилберта при Неизвестньз никакие системы кодирования, для которых было бы доказано, что отношение остается конечным, когда неограниченно возрастает, а отношение остается фиксированным, хотя граница Варшамова — Гилберта показывает, что такие коды существуют.

Теперь рассмотрим коды для двоичного симметричного канала. Из основной теоремы Шеннона для канала с шумом следует, что при любой скорости меньшей, чем пропускная способность канала существуют коды, вероятность ошибки для которых произвольно мала. В настоящее время известна только одна система неслучайного кодирования, а именно безошибочное кодирование Элайеса, описанное в разд. 5.8, для которой вероятность ошибки приближается к нулю, а скорость не стремится к нулю, когда длина кода возрастает; при этом скорость передачи значительно меньше пропускной способности канала.

Имеется еще один заслуживающий внимания факт. Число ошибок, появившихся в блоке из символов при передаче по двоичному симметричному каналу, имеет биномиальное распределение вероятностей со средним значением и стандартным отклонением Доля ошибочно переданных символов имеет поэтому среднее значение и стандартное отклонение Когда неограниченно возрастает, то стандартное отклонение стремится к нулю, и при фиксированном значении вероятность того, что произойдет или больше ошибок, стремится к нулю. С другой стороны, если то вероятность того, что произойдет или больше ошибок, очевидно, не стремится к нулю. Так, код, исправляющий все комбинации из или меньше ошибок и не исправляющий других комбинаций ошибок, будет иметь вероятность ошибки, стремящуюся к нулю, когда неограниченно возрастает, тогда и только тогда, когда . В соответствии с границей Плоткина скорость передачи для такого кода не больше величины, меньшей пропускной способности канала при большем, чем это точка, в которой пересекаются кривые на рис. 4.1. (Пропускная способность канала совпадает с верхней границей Хэмминга, изображенной на рис. 4.1 вместе с границей Плоткина.) Иначе это утверждение может быть сформулировано следующим образом: если при система кодирования реализует пропускную способность канала, то это должно достигаться путем исправления большинства комбинаций из d или меньше ошибок, несмотря на то. что возможно исправление всех комбинаций только из или меньше ошибок, где минимальное расстояние.

Таким образом, хотя лучшие известные в настоящее время коды являются очень хорошими, с точки зрения их практического использования они значительно хуже теоретически возможных пределов, и, несомненно, было бы очень интересно с теоретической точки зрения найти явный способ построения кодов, обладающих по крайней мере теми свойствами, на существование которых указывают найденные границы. Будут ли эти коды представлять практический интерес, зависит от того, насколько реально создание оборудования для их практического использования. Имеется мало сведений относительно теоретических пределов для объема вычислений при декодировании.