Примечания

1 (к § 2.1). Термин, «канал с памятью» укалывает на то, что вероятность ошибки в таком канале зависит от того, как принимались предыдущие символы, т.е. канал как бы хранит в своей памяти предыдущие события.

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

Пусть, например, в двоичном дискретном канале ошибки возникают только под действием некоторого источника помех , причём помеха появляется в случайные моменты времени с вероятностью  и существует некоторая вероятность  того, что если  символ передавался при наличии помехи, то к моменту передачи  символа помехи прекратится (модель Гильберта). Если условная вероятность ошибки при действии помехи равна , то, как легко подсчитать, средняя безусловная вероятность ошибки равна

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

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

В постоянном симметричном канале ошибки независимы. Как известно, отсюда следует, что появление  ошибок в блоке из  символов определяется биномиальным распределением

Поэтому всякий симметричный канал, в котором число ошибок в блоке не подчиняется биномиальному распределению, является каналом с памятью.

2 (к § 2.3). Можно сформулировать условие однозначной декодируемости последовательности символов неравномерного кода. Для существования кода, содержащего  комбинаций, в котором  число символов в -й комбинации, и допускающего однозначное декодирование, необходимо и достаточное условие [40]

                                    (2.72)

где  - основание кода.

Из условия (2.72) можно вывести теорему кодирования для канала без шумов [7].

3 (к § 2.3). В качестве примера практически используемого метода кодирования, приближающегося к экономичному, обычно приводят телеграфный код Морзе. Этот пример не очень удачен, так как код Морзе содержит значительную избыточность, хотя при его разработке был использован принцип выбора наиболее коротких комбинаций для наиболее часто встречающихся букв.

В телеграфной практике существует другой поучительный пример использования статических свойств источника для сокращения среднего числа символов кодовой последовательности, причём использованы не столько одномерные распределения вероятностей букв, сколько вероятностные связи между передаваемыми знаками. Этот пример представляет различные равномерные коды, используемые для буквопечатающего телеграфирования с помощью телеграфных аппаратов, снабжённых «регистрами».

Число букв в алфавите большинства языков не превышает 32. Поэтому можно передавать любые телеграммы, записанные буквами, с помощью 5-разрядного двоичного кода (так как ). Однако помимо букв в телеграммах встречаются иногда цифры и знаки препинания, так что общее количество знаков “алфавита” телеграфного аппарата существенно больше, чем 32. Поэтому примитивное кодирование равномерным двоичным кодом потребовало бы применения шести символов в кодовой комбинации.

Среднее количество символов, приходящихся на знак, существенно сокращается путём применения системы регистров. В простейшем случае телеграфный аппарат имеет два регистра, т.е. два возможных состояния. В первом состоянии (буквенном регистре) передаются и применяются 5-разрядные кодовые комбинации, соответствующие обычным буквам алфавита и пробелу между словами. Во втором состоянии (цифровом регистре) те же кодовые комбинации соответствуют цифрам и знак препинания. Две кодовые комбинации используются для перевода приёмного аппарата с одного регистра на другой.

Легко убедится, что если бы все знаки (включая цифры и знаки препинания) появлялись в телеграммах с равной вероятностью, то применение системы регистров дало бы не экономию а, наоборот, некоторый проигрыш по сравнению с применением примитивного 6-разрядного кода. Действительно, если вероятность того, что очередной передаваемый знак принадлежит к буквенному регистру, равна , то вероятность того, что ровно  знаков подряд будут принадлежать к буквенному регистру, после чего появится знак, принадлежащий к цифровому регистру, равна  То же самое относится и к вероятности того, что ровно  знаков подряд будут принадлежать к цифровому регистру.

Математическое ожидание  числа знаков, идущих подряд до смены регистра равно

Поэтому в среднем через каждые 2 информационных знака будет передаваться знак перевода регистра. Для передачи  знаков потребуется в среднем помимо  символов для самих кодовых комбинаций ещё  символов для комбинаций перевода регистра. Среднее число символов на знак будет равно  т.е. больше, чем при примитивном кодировании 6-разрядным кодом.

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

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

4 (к § 2.7 и 2.8). Простейшим способом корректирующего кодирования является повторение информационных символов. Если каждую разрядную комбинацию примитивного кода повторять  раз, то получится корректирующий код с  и с хемминговым расстоянием . Интересно отметить, что этот код будет систематическим и циклическим. Он по общему правилу позволяет обнаружить ошибки, если их число не превышает , или исправлять ошибки, если их кратность (при нечётном ) не больше . Исправление ошибок здесь производится по правилу большинства, что в симметричном постоянном канале соответствует критерию максимального правдоподобия. Избыточность такого кода  значительно больше, чем у более сложных кодов с таким же хемминговым расстоянием. Этот недостаток лишь в редких случаях окупается простотой декодирования.

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

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

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

5 (к § 2.7 и 2.8). Говоря об ограниченных возможностях обеспечения высокой верности в каналах с шумами путём применения корректирующих кодов с большой длиной блока , мы имели в виду, в первую очередь, трудности кодирования и декодирования. В некоторых случаях, однако, возникают препятствия другого характера, ограничивающие величину , а тем самым и достижимую верность.

При  проходит заметное время между началом и концом приёма блока. Но до окончания приёма блока нельзя приступить к его декодированию. Таким образом, между началом приёма сообщения и выдачей его получателю происходит неизбежная задержка времени, пропорциональная . Если сообщения создаются источником с фиксированной скоростью, то почти такая же задержка происходит при кодировании, поскольку кодовая комбинация может быть сформирована лишь после того, как источник выдаст достаточный объём сообщения. В некоторых системах большая задержка недопустима, поскольку передаваемая информация быстро теряет свою ценность.

6 (к § 2.8). Формула (2.61) является точной, если состояние канала известно обоим корреспондентам. В общем случае для неоднородного канала скорость передачи информации  может быть найдена из полученной А.Н.Колмагоровым [35] формулы «условной информации»:

               (2.73)

где  - скорость передачи информации в последовательности ;   - средняя по всем  скорость передачи информации о состоянии канала, содержащейся в последовательности , когда значения  известны;  - средняя по всем состояниям  скорость передачи информации о последовательности , содержащейся в , когда состояния канала  известны.

Очевидно, что состояние канала  не зависит от передаваемой последовательности , вследствие чего . С учётом этого из (2.73) следует, что

                                                     (2.74)

Так как  (поскольку средняя скорость передачи информации не может быть отрицательной), получим

С другой стороны, в теории информации доказывается, что

где  - энтропия состояния канала, откуда следует

Объединяя полученные неравенства, найдём

                                   (2.75)

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

                                                (2.76)

И так как неравенство (2.75) справедливо при любом распределении , то

                         (2.77)

Но максимум среднего значения нескольких величин не превосходит среднего значения максимумов, откуда

                                 (2.78)

где  — усредненная по состояниям  пропускная способность канала, вычисленная в предположении, что состояния известны.

Если  число состояний не велико и смена их происходит редко, то  из (2.75) следует приближенное равенство

                                                                                                        (2.79)

откуда для случая двух состояний вытекает (2.58).

В работе [41] показано, что при некоторых дополнительных условиях (2.79) перидотит в точное равенство.