Системы передачи информации

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

По характеру сигналов на входе и выходе каналов различают  дискретные, непрерывные и дискретно-непрерывные каналы.

 

1.1.1.Идеальные дискретные каналы

 

Кодер обеспечивает преобразование предаваемых символов в электрические кодовые сигналы. В идеальном канале между элементами кодовых сигналов на входе и выходе существуют однозначное соответствие (ошибки в канале отсутствуют). Скорость передачи информации равна производительности кодера (ф.1):

        C_к =V_кH_к [бит/с].                                         (1)

где V_к=1/L - скорость передачи элементарных кодовых сигналов [сигн./с],

H_к - энтропия кодера [бит/сигн.], L - длительность элементарного кодового

сигнала.

Пропускная  способность идеального канала (ф.2):

               

                            (2)

где m_к - основание кода. Пропускная способность является предельной характеристикой канала. Если основание кода равно m_к и для передачи одного

элементарного кодового сигнала необходимо время L, то для передачи кодовой комбинации длиной n сигналов потребуется время T = nL. Общее число

кодовых комбинаций длительностью T равно N(T) = mⁿ_к. Следовательно, максимальное количество информации в одной кодовой комбинации :     

                 H_макс =nlogm_к.                                         (3)

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

            C=

= V_кlogm_к.                             (4)                                                       

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

Теорема Шеннона для идеального дискретного канала (без доказательства): если ошибки в дискретном канале отсутствуют, можно закодировать сообщение на выходе источника так, чтобы передавать информацию со средней скоростью V, сколь угодно близкой к C. Передавать информацию с V > C невозможно.

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

 

1.1.2.Реальные дискретные каналы

 

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

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

P ( a_i,a′ _j) = P ( a_i)P(a′ _j /a_i) = P(a′ _j)P(a_i /a′ _j) ,          (5)

где P (a_i) и P(a′ _j) - вероятности появления символов a_i и a′ _j, P( a_i /a′ _j)-

условная вероятность.

Обозначим принятый кодовый символ a_k2, а переданный a_i1. Количество информации, которое содержит принятый символ a_k2  относительно переданного a_i1 определяется как

        ₍₆₎

 где P(a_k2,a_{i 1}) - вероятность совместного появления символов a_k2, a_{i 1}; P(a_{i 1}), P ( a_k2) - вероятности появления a_k2, a_i1; P(a_i1/a_k2), P(a_k2/a_i1) -соответствующие условные вероятности. Если символы появляются независимо, то I(a_k2, a_{i 1}) = log1 = 0 . Во всех остальных случаях один символ несет

информацию  о другом и I(a_k2,a_{i 1}) ≠ 0 .

Среднее количество принятой информации, которое приносит один символ, получим, усредняя (6) по всем i и k, а именно:

     

               (7)                                       

Учитывая две формы записи дроби (6), получим две формы записи для количества информации:

  (8)   

           (9)

Выражения (8) и (9) можно записать более наглядно:

I(A₂,A₁)=H(A₁)-H(A₁/A₂) ,                                                                 (10)

I(A₂,A₁) = H(A₂)-H(A₂/A₁) .                                                                (11)

Смысл выражений (10), (11) следующий. Величина H(A₁) - это энтропия кодера, а величина H(A₁/A₂) - это среднее количество информации, потерянное в канале из-за ошибок. Следовательно, соотношение (10) показывает, что среднее количество принятой в одном символе информации можно вычислить как разность энтропий принятого сигнала и помехи. Соотношение (11) используют чаще, так как оно позволяет определить I(A₂,A₁)  через

энтропию помехи, которую определить проще.

Скорость     передачи     информации     в     реальных     каналах     равна

V = V_к I(A₁, A₂). Используя две последние формулы, получим

V = V _к[H(A₁)-H(A₁/A₂)] = V _к[H(A₂)-H(A₂/A₁)] .                                (12)

Если ошибок нет, то H(A₁/A₂) = H(A₂/A₁) = 0 и формула (12) переходит в формулу для идеального канала, когда V = V_max.

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

C = maxV_к[H(A₁)-H(A₁/A₂)] = maxV_к[H(A₂)-H(A₂/A₁)] ,                   (13)

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

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

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

Пропускная  способность реальных каналов

Определим с помощью соотношения (13) пропускную способность реального двоичного симметричного канала без памяти. Предположим, что известна вероятность P₀ появления ошибки в канале.

Определим значение max[H (A₂)-H(A₂/A₁)]. Для двоичного канала maxH(A₂)=log2 = 1 бит/сигн. Условная энтропия H(A₂/A₁) - это энтропия помехи, которая определяется по формуле условной энтропии двоичного источника с коррелированными неравновероятными символами:

H(A₂/A₁) = -P(a₁) [P(a₁/a₁)logP(a₁/a₁) + P(a₂/a₁)logP(a₂/a₁)]-

-P(a₂) [P(a₂/a₂)logP(a₂/a₂) + P(a₁/a₂)logP(a₁/a₂)] .                              (14)

Подставив значения условных вероятностей появления ошибок, получим H(A₂/A₁) = -P(a₁) [(1-P₀)log(1-P₀) + P₀logP₀]-

-P(a₂) [(1-P₀)log(1-P₀) + P₀logP₀] = -[P(a₁) + P(a₂)] [(1-P₀)log(1-P₀) + P₀logP₀] . Так как по условию нормировки сумма вероятностей в первом сомножителе равна единице, то

H(A₂/A₁) = -[(1-P₀)log(1-P₀) + P₀logP₀] .                                               (15)

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

C₂ =V _к[1 + P₀logP₀+(1-P₀)log(1-P₀)] .                                                     (16)

Анализ зависимости   C₂(P₀)   показывает, что  в диапазоне  изменений

P₀∈[0; 0,5]    функция    C₂(P₀)    является    монотонно    убывающей.    При P₀ = 0,5, C₂(P₀) = 0, это означает, что из-за высокого уровня помех в канале кодовые сигналы на входе и на выходе канала становятся независимыми (принимаемые сигналы не несут информации о передаваемых).

Пропускную  способность m-ичного реального канала определяют аналогично

C_m =V_к[logm_к +P₀logP₀(m_к -1)-¹ +(1-P₀)log(1-P₀)] .                              (17)

Из (17) как частный  случай следует (16) при m_к = 2 . Если P₀ → 0 , то пропускная способность реального канала стремится к пропускной способности идеального канала (2).

 

1.2.Полимиальное кодирование

 

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

Пусть a = a0 ... a_m-1 — двоичное сообщение. Тогда сопоставим ему многочлен a(x) = a0 + a1x + … + a_m-1x^m-1. Все вычисления происходят в поле классов вычетов по модулю 2, т. е. от результата любой арифметической операции берется остаток от его деления на 2.

Полиномиальный код с  кодирующим многочленом g(x) кодирует слово сообщения a(x) многочленом b(x) = a(x)g(x) = b₀ +b₁x+···+b_n-1x^n-1 или кодовым словом из коэффициентов этого многочлена b = b₀ ...b_n-1. Условия g₀ = 0 и

g_k = 0 необходимы, потому что в противном случае b₀ и b_n-1 не будут нести никакой информации, т.к. они всегда будут нулями.

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

Рассмотрим (m,n)-код  с кодирующим многочленом g(x). Строка ошибок

e = e₀ ...e_n-1 останется необнаруженной в том и только в том случае, если соответствующий ей многочлен e(x) = e₀ + e₁x + ··· + e_n-1x^n-1 делится на g(x).

Действительно, a(x)g(x) + e(x) делится на g(x) тогда и только тогда, когда e(x) делится на g(x). Поэтому любая ошибка, многочлен которой не делится на g(x), будет обнаружена и, соответственно, любая ошибка, многочлен которой делится на g(x), не может быть обнаружена.

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

Коды Хэмминга можно строить как полиномиальные, например, кодирующий многочлен x³ + x² + 1 определяет совершенный (4, 7)-код. Вообще же, если кодирующий многочлен g(x), порождающий соответствующий (m, n)-код, не является делителем ни одного из многочленов вида x^j +1 при j < n, то минимальное расстояние между кодовыми словами порожденного им кода не меньше 3.

В 1971 году финскими и советскими математиками было доказано [20], что кроме кодов Хэмминга и  Голея других совершенных кодов нет.

Наиболее интересными  среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида b0 ... b_n-2bn-1 есть кодовое слово b_n-1b₀ . . . b_n-2.

1.3. Циклические коды

 

Частным и наиболее широко распространенным классом полиномиальных кодов являются циклические коды.

Линейный (n,k)-код называется циклическим, если в результате циклического сдвига кодового слова получается другое кодовое слово данного кода. Другими словами, если U = (U₀, U₁, ...U_n-1 ) является кодовым словом, то и V = ( U_n-1,U₀,U₁ ,... U_n-2), полученное циклическим сдвигом U, является кодовым словом данного кода.

Циклические коды привлекательны по двум причинам.

Во-первых, операции кодирования и вычисления синдрома для них выполняются очень просто с использованием сдвиговых регистров.

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

Основные свойства циклических кодов:

1.  В циклическом (n,k)-коде каждый ненулевой полином должен иметь степень, по крайней мере (n-k), но не более n-1.

2.   Существует только один кодовый полином g(x) степени (n-k) вида

, называемый порождающим полиномом кода.

3. Каждый кодовый полином U(x) является кратным g(x), то есть

                                    (18)

 

1.3.1. Кодирование с использованием циклических кодов

 

Предположим,    надо    закодировать    некоторую    информационную последовательность т = ( т₀, m₁, m₂...m_k-1 ).

Соответствующий ей полином выглядит следующим образом:

т(х)= m₀+ m₁ x + m₂ x² +...+m_k-1 x^k-1                                              (19)

Умножив т(х)на х^n-k получим полином степени п-1 или меньшей: 
          (20)

 

Воспользовавшись  теоремой о делении полиномов, можно  записать

                        (21)

где   q(x) и р(х) — частное и остаток от деления полинома на порождающий полином g(x).

Поскольку степень g(x)    равна  (п-к),  то степень р(х) должна  быть

(п-к-1) или меньше, а сам полином р(х) будет иметь вид

С  учетом  правил  арифметики  в  GF(2)   данное   выражение  можно переписать следующим образом:

                            (22)

откуда видно, что полином  является кратным g(x) и имеет степень п-1 или меньшую. Следовательно, полином - это кодовый полином, соответствующий кодируемой информационной последовательности т(х).

Раскрыв последнее выражение, получим

что соответствует  кодовому слову

U=	(p0, p1 … pn-k-1,	m0, т1... mk-1),
	проверочные символы	информационные  символы