8.5.3. Пример кодирования линейными блочными кодами

Завершим исследование примером кодирования для простейшего симметричного источника с балансной погрешностью, каким является двоичный симметричный источник с мерой погрешности типа ошибки в символе. Этот пример, рассмотренный Гоблином [1962], показывает, что теорема 8.5.1 справедлива и для линейного двоичного кода.

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

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

Отсюда

Это значит, что код имеющий скорость бит/символ, равен объединению кода имеющего скорость бит/символ со сдвигом

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

Напомним, что выходная последовательность также распределена равномерно, поэтому в совместном ансамбле, объединяющем источник и порождающие векторы, последовательности и и и являются независимыми двоичными векторами. (Проверьте это для а затем обобщите на произвольное целое

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

где указанная вероятность определена на совместном ансамбле векторов При таком построении

а так как векторы независимы, то (8.5.61) можно представить в виде

Левая часть равенства (8.5.63) может быть представлена как среднее по

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

Можно выбрать такую последовательность порождающих векторов что условие (8.5.65) будет выполняться при каждом Для этого набора порождающих векторов находим

где мы воспользовались неравенством и ввели обозна чение Согласно приложению

откуда следует, что существует код для которого

где Следуя тем же рассуждениям, что и при доказательстве теоремы 8.5.1, находим, что при достаточно большом N и любой фиксированной скорости

существует двоичный линейный -код у которого

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