Кодирование. Пропускная способность канала

 

3.1.Основные определения.

Пропускная способность канала

 

Модель системы передачи информации

 

Системой передачи информации называется совокупность технических средств, используемых для передачи информации во времени (хранение информации) или в пространстве (связь). Модель

 

системы передачи информации представлена на рис. 3.1.

 

Рис.3.1

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

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

Канал называется дискретным, непрерывным, дискретно-непрерывным или непрерывно дискретным в зависимости от вида сигналов на его входе и выходе. Если входной А(t) и выходной B(t) сигналы связаны взаимно однозначно, то такой канал называется каналом без шума. В канале с шумом возможны случайные ошибки при преобразовании входного сигнала в выходной.

Дискретный канал с шумом называется каналом без памяти, если ошибки в отдельных символах выходной последовательности статистически независимы. Канал называется стационарным (постоянным), если условные вероятности перехода от А(t) к B(t) не зависят от начала отсчета.

Кодер и декодер. Кодирующее устройство выполняет следующие операции:

а)согласование источника с каналом (перевод реальных сообщений в электрические сигналы, модуляция непрерывных сигналов, квантование непрерывных сообщений, представление s-ичного дискретного сообщения в m-ичном коде и т.п.);

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

Функции декодера в значительной степени обратны функциям кодера. Кроме того, введение при кодировании избыточности в сигнал A(t) часто представляет возможность обнаруживать и исправлять ошибки, возникающие в канале из-за влияния помех. Эта операция тоже выполняется декодирующим устройством.

 

Скорость создания информации.

Скорость передачи информации.

Ненадежность

 

Одной из основных характеристик источника является скорость создания информации. Для стационарного дискретного источника она численно равна энтропии последовательности символов на его выходе, вычисленной по формуле (2.4.2). Скорость создания информации непрерывным источником, вообще говоря, бесконечна. Поэтому в качестве скорости создания информации стационарным непрерывным источником принимает значение e-энтропии непрерывной функции на их выходе, вычисленной при заданной точности воспроизведения этой функции.

Важнейшей характеристикой системы в целом является скорость передачи информации. Скоростью передачи информации называется средняя величина взаимной информации (в единицу времени или на один отсчет) между сигналом X(t) на выходе источника и сигналом Y(t), поступающим к потребителю. Эта величина вычисляется по формуле (2.4.8), но для непрерывных источников в формуле используются значения относительной энтропии (условной и безусловной).

Условная энтропия в правой части выражения (2.4.8) часто называется ненадежностью передачи информации от дискретного источника. Она числено равна разности между скоростью создания информации и скоростью ее передачи, поэтому ненадежность, по существу, есть скорость потери информации в канале (и, возможно, в кодере и декодере). Ненадежность равна нулю только в случае точной передачи информации.

 

Пропускная способность канала

 

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

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

(3.1.1)

где m- основание кода сигнала, используемого в канале (см. 3.2.2). Скорость передачи информации в дискретном канале без шумов равно его пропускной способности, когда символы в канале независимы, а все m букв равновероятны.

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

.(3.1.2)

При заданных вероятностях перехода p(b_k/a_j) задача вычисления пропускной способности сводится к отысканию “наилучшего” распределения вероятностей p(a₁),…,p(a_m), букв на входе канала. Скорость передачи информации в таком канале равна его пропускной способности, когда символы в канале независимы, а распределение вероятностей m входных букв равно найденному.

Пропускная способность непрерывного канала с ограниченной полосой частот Df Гц, в котором действует аддитивный белый гауссов шум со спектральной плотностью N₀ Bт/Гу , вычисляется по формуле Шеннона-Таллера

(3.1.3)

где P_c= M[A²(t)]-средняя мощность стационарного выходного сигнала А(t), Р_ш=N₀Df-средняя мощность шума, попадающего в полосу частот Df.

Скорость передачи информации в непрерывном канале равна его пропускной способности, когда входной сигнал А(t) также является стационарным гауссовым случайным процессом с нулевым средним и энергетическим спектром, равномерным в полосе частот Df.

 

3.2.КОДИРОВАНИЕ В ДИСКРЕТНЫХ КАНАЛАХ БЕЗ ШУМОВ

 

Общие принципы кодирования

 

Дискретным m-ичным каналом без шумов называется канал, в котором сигналы на входе А(t) и выходе B(t) являются последовательностями дискретных случайных величин - символов с основанием кода m, причем входной и выходной сигналы связаны взаимно однозначно (см. рис. 3.1).

Пропускная способность такого канала равна наибольшей возможной энтропии сигнала A(t) на его входе

Из (2.4.5) имеем

(3.2.1)

где F_k- частота следования символов в канале, симв/с.

Пусть Х⁽¹⁾, Х⁽²⁾, …- последовательность символов s-ичного источника сообщений при многократном независимом выборе. Тогда скорость создания информации равна

Н=Н(Х)F_и , (3.2.2)

где F_и- частота следования символов источника, Н(Х)-энтропия алфавита источника.

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

Кодирующее устройство должно удовлетворять двум основным требованиям:

1.Обеспечить безошибочную передачу информации, т.е. взаимно однозначное соответствие между X(t) и A(t) (см. рис.3.1).

2.Осуществить кодирование наиболее экономным образом (с минимальной избыточностью).

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

Для осуществления возможности разделения кодовых слов применяется одна из следующих мер:

1. Использование специальной буквы.

2. Применение кодовых слов одинаковой длины без разделительных букв - равномерное кодирование.

3. Кодовая таблица составляется так. Чтобы никакое кодовое слово не являлось началом другого более длинного.

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

, (3.2.3)

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

Средняя длина кодового слова ограничена снизу, так как для безошибочной передачи информации необходимо выполнение соотношения Н£С. Это обстоятельство сформулировано в теореме Шеннона о кодировании в дискретных каналах без шумов.

Теорема. При кодировании множества сигналов с энтропией Н(Х) при условии отсутствия шумов средняя длина кодового слова не может быть меньше, чем Н(Х)/log m, где m-основание кода. Если вероятности сигналов не являются целочисленными отрицательными степенями числа m, то точное достижение указанной нижней границы невозможно, но при кодировании достаточно длинными блоками к ней можно сколь угодно приблизиться.

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

1.Более вероятным буквам источника соответствуют более короткие кодовые слова (принцип статистического кодирования).

2.Никакое кодовое слово не является началом другого, более длинного.

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

4.Символы в последовательности на входе кодера практически независимы.

Наилучшим среди этих кодов является код, предложенный Д.А.Хаффманом.

 

Код Хаффмана

 

Кодирование по методу Хаффмана осуществляется следующим образом:

1. s букв алфавита источника располагаем в порядке убывания их вероятностей.

2. Выбираем целое число m₀ такое, что

где а – целое положительное число.

При кодировании в двоичном канале m₀=m=2.

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

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

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

5.Буквы нового алфавита, полученного на 4-м шаге, располагаем в порядке убывания вероятностей.

6.Осуществляем последовательное сжатие алфавита путем повторения операций 4 и 5, пока в новом алфавите не останется единственная буква.

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

Код Хаффмана имеет среднюю длину кодового слова меньшую (или равную), чем любой другой код.

 

Код Шеннона-Фано

 

Кодирование осуществляются следующим образом:

1.s букв алфавита источника располагаем в порядке убывания вероятностей.

2.Делим алфавит источника на m групп так, чтобы общие вероятности букв в каждой из групп были примерно равны. В качестве первого символа кодового слова выбираем 0,1,…,m-1, в зависимости от того, в которой из групп оказалась кодируемая буква.

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

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

 

Блоковое кодирование

 

Выше были рассмотрены способы побуквенного кодирования, когда каждой букве на выходе источника приписывалось свое кодовое слово. Таковой способ кодирования позволяет достигнуть минимальной средней длины кодового слова, равной Н(Х)/log m, только в том случае, когда вероятности букв являются отрицательными целочисленными степенями числа m. Если вероятности не удовлетворяют этому требованию, избыточность при побуквенном кодировании может оказаться недопустимо большой. В таком случае применяют блоковое кодирование.

При кодировании блоками по k букв, прежде всего, строят вспомогательный алфавит, состоящий из N=s^k букв, так что каждой букве этого алфавита соответствует своя комбинация (блок) из k букв алфавита источника. Вероятность буквы z_ij…_q вспомогательного алфавита, соответствующей комбинации x_ix_j…x_q, вычисляется по формуле

 

p(z_ij…_q) = p(x_i) p(x_j)…p(x_q). (3.2.4)

Далее буквы вспомогательного алфавита располагаются в порядке убывания вероятностей, и осуществляется кодирование методом Шеннона-Фано или Хаффмана.

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

 

 

3.3. КОДИРОВАНИЕ В ДИСКРЕТНЫХ КАНАЛАХ С ШУМАМИ

 

Теоремы Шеннона о кодировании в дискретных каналах с шумами

Дискретным каналом с шумом называется канал, в котором сигналы А(t) и В(t) (см. рис. 3.1) являются последовательностями символов, однозначная связь между входными и выходными сигналами отсутствует, и поэтому передача символов в канале сопровождается случайными ошибками.

Ответ на вопрос о возможности безошибочной передачи информации дается теоремами Шеннона о кодировании в дискретных каналах с шумами.

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

Обратная теорема. Если Н>С, то никакой код не сможет сделать вероятность ошибок сколь угодно малой и достигнуть ненадежности, меньшей, чем Н-С. Основной способ повышения помехоустойчивости системы передачи информации - разумное введение избыточности в передаваемый сигнал А (t).

 

Корректирующие коды

 

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

Пусть а₁, а₂, ..., а_s - двоичные кодовые слова длиной в n символов каждое, соответствующие s буквам алфавита источника. Каждое кодовое слово можно формально рассматривать как вектор-строку, соответствующий некоторой точке в n-мерном пространстве.

Расстояние Хэмминга d_jk между двумя кодовыми словари a₁ и а₂ равно числу символов, в которых эти слова отличаются одно от другого.

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

Таблица 3.3.1

0Å0=0	0Å1=1
1Å0=1	1Å1=0

 

Сложение и вычитание по модулю 2 эквивалентны.

Расстояние между двумя кодовыми словами можно теперь определить как количество единиц в кодовом слове, полученном при суммировании этих слов по модулю 2.

Наименьшее значение расстояния между словами в выбранной системе кодирования называется кодовым расстоянием d_код.

Считают, что в канале произошла q-кратная ошибка, если кодовое слово на выходе канала отличается от кодового слова на его входе ровно в q символах (т. е. расстояние между этими словами-векторами равно q). Таким образом, вектор на выходе канала равен сумме по модулю 2 входного вектора и вектора ошибки.

Код позволяет обнаруживать любую ошибку кратности q₀, если его кодовое расстояние удовлетворяет условию

(3.3.1)

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

(3.3.2)

 

Систематические коды

 

Среди всех корректирующих кодов наибольшее применение нашли систематические коды. Систематическим кодом (n,k) называется двоичный корректирующий код, удовлетворяющий следующим требованиям:

1. Все кодовые слова содержат по n символов, из которых k символов - информационные, а остальные n-k символов - проверочные. Информационные и проверочные символы занимают в кодовом слове определенные позиции.

2. Сумма по модулю 2 любых двух кодовых слов снова дает кодовое слово принадлежащее данному систематическому коду.

Систематический код задается производящей (порождающей) матрицей G, имеющей k строки n столбцов. Строки производящей матрицы должны быть линейно независимыми, т. е. сумма любых строк (по 2, по 3 и т.д. в любых комбинациях) не должна давать нулевое слово (состоящее из одних нулей).

Следующим этапом в построении систематического кода является определение проверочной матрицы Н, имеющей r=n-k строк и n столбцов. Любой вектор - строка проверочной матрицы Н ортогонален любому вектору - строке производящей матрицы G, следовательно,

(3.3.3)

где - транспонированная матрица G. Заметим, что два вектора u=u₁,...,u_n и v= v₁,.., v_1n являются, по определению, ортогональными, если

Работа кодера для (n,k) -кода заключается в том, что к поступающему на его вход k-разрядному вектору информационных символов x он должен добавить r проверочных символов. Правило образования кодового слова а определяется соотношением

(3.3.4)

Умножив обе части этого выражения на и учитывая (3.3.3), получим другое соотношение, определяющее функции кодера

(3.3.5)

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

Один из способов декодирования принятого вектора b предусматривает вычисление r-разрядного исправляющего вектора (синдрома) c по правилу

(3.3.6)

Из формулы (3.3.5) следует, что значение синдрома определяется только вектором ошибки. Если с¹0, делают заключение о наличии ошибки (обнаружение ошибки). Так как различным ошибкам кратности q_и, удовлетворяющей неравенству (3.3.2), соответствуют различные значения синдрома, то вычисленное значение с однозначно определяет положение символов, в которых произошли такие ошибки. Эти ошибки исправляются в декодере суммированием принятого вектора b с соответствующим вектором ошибок.

Основными элементами кодирующих и декодирующих устройств для систематических кодов являются сумматоры по модулю 2 и сдвигающие регистры. Сдвигающим регистром называют цепочку, состоящую из двоичных ячеек, меняющую свое состояние в дискретные моменты времени (шагами). На каждом шаге двоичный символ, имеющийся на входе ячейки, перемещается на ее выход.

Ниже приведены краткие данные наиболее распространенных систематических кодов.

Код Хэмминга с кодовым расстоянием 3 полностью характеризуется числом проверочных символов r. Общее число символов в кодовом слове равно n=2^r-1. В качестве столбцов проверочной матрицы Н выбираются всевозможные r-разрядные двоичные числа, исключая число нуль.

Код Рида-Мюллера полностью характеризуется двумя целыми положительными числами: m³3 и d<m. Число d называется порядком кода. Остальные параметры кода определяются из соотношений:

(3.3.7)

Первая строка производящей матрицы G состоит из единиц. Следующие m строк (базисные векторы первого порядка) можно получить, если записать n столбцов, состоящих из m-разрядных двоичных чисел. Следующие C_m² строк (базисные векторы второго порядка) получают, вычисляя скалярные произведения различных пар базисных векторов первого порядка, и т.д. до получения базисных векторов d-го порядка.

Циклической код полностью определяется первой строкой производящей матрицы G. Остальные строки получают в результате циклического сдвига первой строки на 1,2,.., k-1 элементов. Таким же циклическим свойством обладает и проверочная матрица Н.