Пользователь
0,0
рейтинг
29 октября 2013 в 16:09

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

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

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

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

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

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

image

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

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


Обратная теорема:
Если скорость передачи больше пропускной способности, то есть, то не существует таких способов передачи, при которых вероятность ошибки стремится к нулю при увеличении длины передаваемого блока.
Wiki

Для аддитивного белого гауссова шума Шеннон получил следующее выражение:
image, где
C — пропускная способность канала, бит/с;
W — ширина полосы канала, Гц;
S — мощность сигнала, Вт;
N — мощность шума, Вт.

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

image, где
η — эффективность использования спектра, бит/с/Гц;
TR — скорость передачи информации, бит/с;
W — ширина полосы канала, Гц.

Тогда, image, используя значение энергии бита (для сигналов со сложными сигнально кодовыми конструкциями я понимаю среднее значение энергии на бит) и image, где
k — количество бит на символ, передаваемый в канал;
T — длительность символа, с;
R — скорость передачи в канале, бит/с;
Eb — энергия на передачу одного бита в канале;
N0 — спектральная плотность мощности шума, Вт/Гц;
получим image или image.

Предел Шеннона будет иметь вид:
image

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

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

Литература


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

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

Подробнее
Реклама

Самое читаемое

Комментарии (9)

  • 0
    Конспект Шеннона, это хорошо. Поправьте меня, если ошибаюсь, Вы энергией энтропию назвали?
    Насколько Вы глубоко во всём этом?
    Мне пришлось столкнуться с этой областью, но несколько с другой стороны. Знакомы ли вы с трудами Бонгарда сотоварищи, когда важнее оценить не просто количество переданной информации, а именно её полезность в контексте определённой задачи? Вот это на мой взгляд более интересно было-бы рассмотреть.
    • +1
      Хотел именно энергию рассматривать, энтропийная запись у Шеннона кажется относится к сжатию информации.
      Глубоко ли… Проходили много чего, выглядело красиво, когда возникла необходимость применять на практике возникло много вопросов, пытаюсь разбираться глубже и заодно оставить описание «на пальцах».
      С трудами Бонгарда не знаком, можете пояснить про полезность?
      • +1
        Энтропия не для сжатия, а для оценки количества информации. Какое количество информации несёт каждый переданный по каналу бит. С её помощью можно перейти от оценки непосредственной пропускной способности канала в сигналах к информационной пропускной способности. Чем большую неопределённость ликвидировало поступившее сообщение, тем большим было количество переданной им информации.
        Все эти вещи очень базовые для теории передачи информации. Используются очень широко.
        Но вот, что интересно, все оценивают информационную пропускную способность и никого не волнует, а на сколько полезна переданная информация. Т.е. информации передали много, ОК, круто, всё.
        Понятно, что полезность одной и той же информации зависит от решаемой задачи и уже имеющейся информации. Она может быть даже отрицательной — дезинформация. М.Бонгард в книге «Проблемы узнавания» предложил формальную модель для описания всего этого. Но к сожалению погиб не продвинувшись в этом. А его продолжатели ушли в сторону. Сейчас появляются попытки работать в этой области, но больше все в семантический анализ копают…
        Вот я и спросил, может Вы слышали что-либо об этом, раз занимаетесь в этой сфере, может что-то новое появилось.
        Такие дела…
        • 0
          Энтропия больше относится к источнику и выбору алфавита, пропускная способность канала должна согласовываться с итоговой скоростью передачи информации в системе. Я старался рассматривать кодер канала.
          • 0
            ОК. Ну понятно, чуть разные вещи всё же
        • +1
          Рекомендую Колмогорова почитать, он как раз полезность рассматривал. Насколько я помню, полезность, правда, больше характеризует потребителя/наблюдателя чем сам сигнал, поэтому либо надо делать модель пары источник-наблюдатель, что в общем случае невозможно, т.к. потребует составить чуть ли не модель всего окружающего, либо забыть этот страшный сон и ограничиться сигналом, что неверно в полной очевидности — без наблюдателя информации не существует в принципе. Колмогоров предлагал компромисс — длина алгоритма позволяющего восстановить данный сигнал средствами получателя. Так себе, ни лево, ни право, но работает лучше чем Шеннон, как раз в описываемом вами случае. Намного лучше. И формализации поддается со всех сторон, что приятно. У него же я первый раз встретил термин «качество информации», видимо он его и ввел, хронологически. Но математика и кругозор там такие, что тонкости я ниасилил, а философия там сугубо математически-прикладная. Воды нет вообще. Судя по тому, что данное предложение что-то не развилось никуда, наверное не только я ничего там не понял, остальные тоже. Все таки вопрос инженерный, а там Математик с большой буквы. Жалко, что Неш этим делом не занялся, а ведь как близко был…
          И это не новое, да. И Бонгарда я читал. Не понравилось.
          • 0
            Спасибо большое. Посмотрю. Боюсь суровая математика мне не по зубам, я больше по алгоритмам, программированию, computer science / data mining. Но Бонгард отчасти привлёк не таким зубодробительным мат-аппаратом, что я смог разобраться более-менее.
  • 0
    Начиная с названия, автор не определяет, что такое эффективность передачи данных.
    Не определяет автор и данные. Какие задачи теории информации (опять же, что это
    означает для автора) рассматриваются в работе не определено.
    >Таким образом видим, что существует предел отношения сигнал/шум в канале (Eb/N0) такой, что невозможно построить систему передачи данных, в которой можно добиться сколь угодно малой вероятности ошибки, при большем уровне шума (может существовать система с просто малой вероятностью ошибки, при предельном отношении!).
    О какой и чего ошибке идет речь? Как вычисляется вероятность? Каким методом?
    Если можете поясните, Спасибо.
    • 0
      Эффективность сама по себе может подразумевать эффективность использования спектра/мощности/скорости передачи данных при прочих раных условиях.
      Данные как и информация сущность абстрактная, в данном случае я попытался описать процесс кодирования источника и в дальнейшем рассматривал цифровую информацию.
      Задача — определение границы Шеннона для канала передачи данных с белым гауссовым шумом.
      Ошибка передачи данных суть сравнение набора переданных бит с принятым (отношение числа ошибочно принятых к общему числу).
      Вероятность ошибки для канала с АБГШ рассчитывается теоретически исходя из распределения шума.

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