2.10. Сравнение кодов по их близости к границе Шеннона

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

2.10. Сравнение кодов по их близости к границе Шеннона

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

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

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

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

Различные формы кодирования для преобразования аналоговых сигналов в цифровые, их хранения, передачи и преобразования обратно в аналоговую форму начали своё бурное развитие во второй половине XX века, и к началу XXI практически вытеснили аналоговые системы.

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

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

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

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

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

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

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

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

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

, где

C — пропускная способность канала, бит/с; W — ширина полосы канала, Гц; S — мощность сигнала, Вт; N — мощность шума, Вт.
(График для наглядности, зависимость C(W,P) при N0=const; значения с потолка, попрошу на них не смотреть)
Т.к. мощность АБГШ растёт линейно с шириной полосы канала, имеем, что пропускная способность канала имеет предел Cmax=(S/N0)log(2), при бесконечно широкой частотной полосе (который растёт линейно по мощности).

, где

η — эффективность использования спектра, бит/с/Гц;

TR — скорость передачи информации, бит/с;

W — ширина полосы канала, Гц.

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

k — количество бит на символ, передаваемый в канал; T — длительность символа, с; R — скорость передачи в канале, бит/с;

Eb — энергия на передачу одного бита в канале;

N0 — спектральная плотность мощности шума, Вт/Гц;
получим или . Предел Шеннона будет иметь вид:

Данный предел имеет смысл для каналов без кодеков (R = TR), для достижения такой эффективности принимаемое слово должно быть бесконечной длины.

Для каналов с использованием кодеков помехоустойчивого кодирования под Eb следует понимать энергию на передачу одного информационного, а не канального бита (тут возможны разночтения и я готов выслушать альтернативные версии) => Eb/N0 в канале отлично от этого значения в зависимости от скорости кода (1/2, 3/4, 7/8… )

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

Литература

Галлагер Р. «Теория информации и надёжная связь» – М.: «Советское радио», 1974.
Сэломон Д. «Сжатие данных, изображений и звука» – М.: «Техносфера», 2004

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

  • АБГШ
  • теория информации
  • надёжность
  • Шеннон

Источник: https://habr.com/post/199488/

9.4. Теорема Шеннона-Хартли о пропускной способности канала. 9. Компромиссы при использовании модуляции и кодирования. Теоретические основы цифровой связи

2.10. Сравнение кодов по их близости к границе Шеннона

9.4.1. Предел Шеннона

9.4.2. Энтропия

9.4.3. Неоднозначность и эффективная скорость передачи информации

Шеннон [3] показал, что пропускная способность канала C с аддитивным белым гауссовым шумом (additive white Gaussian noise — AWGN) является функцией средней мощности принятого сигнала S, средней мощности шума N и ширины полосы пропускания W. Выражение для пропускной способности (теорема Шеннона-Хартли) можно записать следующим образом.

(9.2)

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

Если же , то кода, на основе которого можно добиться сколь угодно малой вероятности возникновения ошибки, не существует. В работе Шеннона показано, что величины S, N и W устанавливают пределы скорости передачи, а не вероятности появления ошибки. Шеннон [4] использовал уравнение (9.

2) для графического представления доступных пределов производительности прикладных систем. Этот график, показанный на рис. 9.2, представляет нормированную пропускную способность канала C/W в бит/с/Гц как функцию отношения сигнал/шум (signal-to-noise ratio — SNR) в канале. График, представленный на рис. 9.

3, изображает зависимость нормированной полосы пропускания канала W/C в бит/с/Гц от отношения сигнал/шум канала. Иногда рис. 9.3 используется как иллюстрация компромисса между мощностью и полосой пропускания, присущего идеальному каналу.

Однако это не совсем компромисс [5], поскольку мощность обнаруженного шума пропорциональна полосе пропускания.

(9.3)

Подставив выражение (9.3) в уравнение (9.2) и немного преобразовав последнее, получаем следующее.

(9.4)

Если битовая скорость передачи равна пропускной способности канала (R = С), то с помощью тождества (3.30) можно записать следующее.

(9.5)

Рис. 9.2. Зависимость нормированной пропускной способности канала от SNR канала

Рис. 9.3. Зависимость нормированной полосы пропускания канала от SNR канала

Таким образом, уравнение (9.4) можно модифицировать следующим образом.

(9.6, а)

(9.6 б)

(9.6 в)

На рис. 9.4 представлен график зависимости W/C от , описываемой формулой (9.6, в); асимптотическое поведение этой кривой при C/W (или W/C) рассматривается в следующем разделе.

Рис. 9.4. Зависимость нормированной полосы пропускания канала от

9.4.1. Предел Шеннона

Существует нижнее предельное значение Et/N0, при котором, ни при какой скорости передачи нельзя осуществить безошибочную передачу информации. С помощью соотношения

можно рассчитать граничное значение .

Пусть

Тогда, из уравнения (9.6,а),

и

В пределе, при C/W, получаем

= 0,693 (9.7)

или, в децибелах,

= -1,6дБ

Это значение называется пределом Шеннона (Shannon limit). На рис. 9.1, а предел Шеннона — это кривая зависимости РВот при k. При = -1,6 данная кривая скачкообразно изменяет свое значение с РВ= 1/2 на РВ =0.

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

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

При вероятности появления битовой ошибки 10-5 двоичная фазовая манипуляция (binary phase-shift-keying — BPSK) требует значения , равного 9,6 дБ (оптимум некодированной двоичной модуляции).

Следовательно, в данном случае в работе Шеннона указано, что теоретически, за счет использования кодирования, производительность можно повысить на 11,2 дБ по сравнению с некодированной двоичной модуляцией. В настоящее время большую часть такого улучшения (почти 10 дБ) можно получить с помощью турбокодов (см. раздел 8.4).

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

9.4.2. Энтропия

Для разработки системы связи с определенной способностью к обработке сообщений нужна метрика измерения объема передаваемой информации.

Шеннон [3] ввел такую метрику Н, называемую энтропией источника сообщений (имеющего л возможных выходных значений).

Энтропия (entropy) определяется как среднее количество информации, приходящееся на один выход источника, и выражается следующим образом.

бит/выход источника (9.8)

Здесь piвероятность i-гo выходного значения и =1. Если сообщение двоичное или источник имеет только два возможных выходных значения с вероятностями р и , выражение для энтропии примет следующий вид.

(9.9)

Зависимость энтропии от р показана на рис. 9.5.

Рис. 9.5. Зависимость энтропии от вероятности (два события)

Величина Н имеет ряд особенностей.

1. Если логарифм в уравнении (9.8) берется по основанию 2, единица измерения Н — среднее число бит на событие. Здесь единица измерения бит — это мера количества информации, и ее не следует путать с термином «бит», означающим «двоичная цифра» (binary digit — bit).

2. Сам термин «энтропия» имеет несколько неопределенный смысл, что вызвано наличием нескольких формулировок в статистической механике. Для информационного источника с двумя равновероятными состояниями (например, выбрасывание монеты правильной формы) из рис. 9.

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

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

3. Для иллюстрации связи между количеством информации и априорной вероятностью (если априорная вероятность сообщения на приемнике является нулем или единицей, сообщение можно не посылать) рассмотрим следующий пример. После девятимесячной беременности женщина оказывается в родильной палате. Муж с волнением ждет в приемной.

Через некоторое время к нему подходит врач и говорит: «Примите мои поздравления, вы стали отцом». Какую информацию отец получил от врача после медицинского исхода! Почти никакой; отец практически достоверно знал, что ребенок должен родиться.

Если бы врач сказал, «вы стали отцом мальчика» или «вы стали отцом девочки», он передал бы 1 бит информации, поскольку существует 50% вероятность того, что ребенок окажется девочкой или мальчиком.

Пример 9.2. Среднее количество информации в английском языке

а) Найдите среднее количество информации в бит/знак для английского языка, считая, что каждая из 26 букв алфавита появляется с равной вероятностью. Пробелы и знаки пунктуации не учитываются.

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

р = 0,10: для букв а, е, о, t

р = 0,07: для букв h, i, n, r, s

р=0,02: для букв с, d, f, I, m, p, u, у

р = 0,01: для букв b, g, j, k, q, v, w, x, z

Решение

а) =4,7 бит/знак

б) = = 4,17 бит/знак

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

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

9.4.3. Неоднозначность и эффективная скорость передачи информации

Пусть по двоичному симметричному каналу (определенному в разделе 6.3.1) со скоростью 1000 двоичных символов/с происходит передача информации, а априорная вероятность передачи нуля или единицы одинакова.

Допустим также, что помехи в канале настолько значительны, что, независимо от переданного символа, вероятность приема единицы равна 1/2 (то же самое — для нуля).

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

Одинаково «хороший» прием дает и использование «информации», поступившей из канала, и генерация этой «информации» методом подбрасывания правильной монеты. Утраченной является информация о корректности переданных символов. Для оценки неопределенности в принятом сигнале Шеннон [3] использует поправочный коэффициент, который называет неоднозначностью (equivocation).

Шеннон показал, что среднее эффективное количество информации Н в приемнике получается путем вычитания неоднозначности из энтропии источника.

Для системы, передающей равновероятные двоичные символы, энтропия Н(Х) равна 1 бит/символ. Если символы принимаются с Рв = 0,01, неоднозначность, как показано выше, равна 0,081 битДпринятый символ). Тогда, используя уравнение (9.11), можем записать эффективную энтропию Rед принятого сигнала.

Rед = 1 — 0,081 = 0,919 бит/полученный символ

Иными словами, если, например, за секунду передается R = 1000 двоичных символов, то Reff можно выразить следующим образом.

Reff = RHeS = 1000 символов/с х 0,919 бит/символ = 919 бит/с (9.12)

Отметим, что в предельном случае Рв= 0,5

Используя формулы (9.12) и (9.11) при R= 1000 символов/с, получаем

что и следовало ожидать.

Пример 9.3. Кажущееся противоречие с пределом Шеннона

График зависимости Pb от Eb|N0 обычно показывает плавный рост Рвпри увеличении Eb|N0. Например, кривые вероятности появления битовых ошибок на рис. 9.

1 показывают, что в пределе при Eb|N0, стремящемся к нулю, Pb стремится к 0,5.

Таким образом, кажется, что всегда (при сколь угодно малом значении Eb|N0) имеется ненулевая скорость передачи информации.

На первый взгляд это не согласуется с величиной предела Шеннона Eb|N0= -1,6 дБ, ниже которого невозможна безошибочная передача информации или ниже которого даже бесконечная полоса пропускания дает конечную скорость передачи информации (см. рис. 9.4).

а) Предложите способ разрешения кажущегося противоречия.

б) Покажите, каким образом коррекция неоднозначности по Шеннону может помочь разрешить данное противоречие для двоичной системы с модуляцией PSK, если энтропия источника равна 1 бит/символ. Предположим, что рабочая точка на рис. 9.1, б соответствует Eb|N0= 0,1 (-10 дБ).

Решение

а) Величина Eb, традиционно используемая при расчетах каналов в прикладных системах, — это энергия принятого сигнала, приходящаяся на переданный символ.

Однако Eb, в уравнении (9.6) — это энергия сигнала, приходящаяся на один бит принятой информации.

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

б) На основе уравнения (4.79) для BPSK можно записать

.

где Q определено в формуле (3.43) и представлено в табличной форме в приложении Б (табл. Б.1). Из таблицы находим, что РВ = 0,33. Далее находим неоднозначность и эффективную энтропию.

Следовательно,

Таким образом, эффективное значение Eb|N0 равно 0,7 дБ на принятый информационный бит, что значительно больше предела Шеннона -1,6 дБ.

Источник: https://siblec.ru/telekommunikatsii/teoreticheskie-osnovy-tsifrovoj-svyazi/9-kompromissy-pri-ispolzovanii-modulyatsii-i-kodirovaniya/9-4-teorema-shennona-khartli-o-propusknoj-sposobnosti-kanala

12.2. Предельная эффективность телекоммуникационных систем и граница к. Шеннона

2.10. Сравнение кодов по их близости к границе Шеннона

показателии имеют смысл удельныхскоростей,а обратные величины = 1/и = 1/определяют удельныерасходы соответствующихресурсов на передачу информации сединичной скоростью(1бит/с).

Длягауссовского канала с полосой пропусканияFк,отношением мощностей сигнала и шума= Pc/Pши пропускной способностью можноустановить, что эти показателиэффективности связаны соотношением:

и (12.4)

Дляидеальной системы (= 1)может быть определена предельнаязависимость.Согласно теореме Шеннона, присоответствующих способах передачи(кодирования и модуляции) и приема(демодуляции и декодирования), величинаможет быть скольугодно близкой к единице.При этом ошибка может быть сделана скольугодно малой.В этом случае из условия =1 получаем предельную зависимость междуи :

(12.5)

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

Эту зависимость удобно представлять ввиде кривой на плоскости  = f()(«Предел Шеннона»). Эта кривая являетсяпредельнойи отражает наилучшийобмен междуивнепрерывном канале (НК).

Следует заметить, что частотнаяэффективностьизменяется в пределах от 0 до ,в то время как энергетическая эффективностьограничена сверху величиной

. (12.6)

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

. (12.7)

Вреальных цифровых системах передачивероятность ошибки pвсегда имеет конечное значение иинформационная эффективность меньшепредельной эффективности макс.В этих случаях для фиксированнойвероятности ошибки = constможноопределить коэффициенты эффективностии ипостроить кривые  = f().

В координатах (, )каждому варианту системы передачиинформации будет соответствовать точкана плоскости.Все эти точки (кривые) должны располагатьсянижепредельной кривой Шеннона.

Ход этих кривых зависит от вида сигналов(модуляции), кода (метода кодирования)и способа обработки сигналов(демодуляции/декодирования).

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

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

12.3. Перспективные пути дальнейшего повышения эффективности телекоммуникационных систем

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

В предыдущих модулях курса ТЭС изучалисьотдельные устройства (элементы) ЦТКС ипроисходящие в них процессы. В результатетакого раздельного(поэлементного) анализа полученыалгоритмы функционирования кодекаисточника, модема и, соответственно,кодека канала.

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

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

Вмодуле 1 были изучены свойства широкогокласса сигналов цифровых модуляций иметоды их формирования. Анализ показывает,что, изменяя свойства дискретныхсигналов-переносчиковинформациипо каналу связи, можно в широких пределахизменять показатели эффективностиЦТКС.

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

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

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

Источник: https://studfile.net/preview/5157419/page:21/

Scicenter1
Добавить комментарий