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

Помехоустойчивое кодирование. Теорема Шеннона

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

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

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

В соответствии с теоремой о эффективном кодировании среднее количество символов на одну букву l_ср ≥ Н(х), т.е. в первом приближении можно получить, что

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

Теорема о помехоустойчивом кодировании требует чтобы

где l_ср – средняя длина кодовой комбинации для записи одной буквы.

По сравнению с эффективным кодом l_ср увеличивается до:

Однако, такой величины l_ср1 помехоустойчивые коды не достигают. Это можно рассматривать как теоретический предел.

Источник

1. Первая теорема Шеннона. Основные понятия

Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:

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

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

Код — (1) правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита.

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

Кодирование — перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.

Декодирование — операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.

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

Декодер — устройство, производящее декодирование.

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

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

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

Как следует из (3.4), минимально возможным значением средней длины кода будет:

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

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

Из (3.5) видно, что имеются два пути сокращения К min (А,В):

В качестве меры превышения К(А,В) над K min (А,В) можно ввести относительную избыточность кода (Q(А,В):

Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, Q(A,B) → 0 при К(А,В) → К min (А,В). Следовательно, решение проблемы оптимизации кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению К min (А,В), равному отношению средних информации на знак первичного и вторичного алфавитов. Чем меньше Q(A,B), тем I_fin(В) ближе к I_st(A)), т.е. возникает меньше информации, связанной с кодированием, более выгодным оказывается код и более эффективной операция кодирования.

Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:

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

и первая теорема Шеннона получает следующую интерпретацию:

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

Применение формулы (3.7) для двоичных сообщений источника без памяти при кодировании знаками равной вероятности дает:

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

Возможны следующие особенности вторичного алфавита, используемого при кодировании:

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

Источник

Информационная теория

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

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

Основная теорема Шеннона о кодировании

Важный практический вопрос при обработке информации — какова мощность системы передачи данных. Можно получить определённый ответ, используя уравнение Шеннона. Оно позволяет точно понять информационную пропускную способность любого сигнального канала. Формула Шеннона в информатике: I = — (p1log2 p1 + p2 log2 p2 +. + pN log2 pN)

Основная теория Шеннона о кодировании для дискретного канала с помехой, приведённая здесь без доказательства, аналогична теореме канала не имеющего помех: если источник данных с энтропией H (Z), а канал связи имеет ширину полосы C, то сообщения, сгенерированные источником, всегда могут быть закодированы так, чтобы их скорость передачи vz была произвольно близка к значению: vzm = C | H (Z).

Не существует метода кодирования, который бы позволял передавать со скоростью, превышающей vzm, и с произвольно низкой вероятностью ошибки. Другими словами, если поток информации: H ‘(Z) = vz * H (Z) C он не существует.

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

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

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

Это приводит к замечательному выводу:

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

Условие применения формулы Шеннона — избыточность, создаёт предсказуемые отношения между различными участками сигнального устройства. Хотя это снижает эффективность передачи информации в системе, но помогает отличать детали сигнала от случайного шума. Здесь обнаружена максимально возможная информационная пропускная способность системы. Поэтому нужно избегать избыточности и позволять сигналу иметь «непредсказуемые» качества, которые делают его статистически похожим на случайный шум.

Передача сигналов

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

Это означает:

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

Это означает, что в такой системе, большинство сообщений будет одинаковый уровень мощности. В идеале каждое ИС должно иметь одинаковый, максимально возможный уровень мощности. На самом деле можно повернуть этот аргумент с ног на голову и сказать, что «типичны» только сообщения со средними силами, подобными этому максимуму. Те, что обладают гораздо более низкими способностями, необычны — то есть редки.

Определённое уравнение

Сигнал и шум не коррелированны, то есть они не связаны каким-либо образом, который позволит предсказать один из них. Суммарная мощность, получаемая при объединении этих некоррелированных ИС, по-видимому, случайно изменяющихся величин, задаётся.

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

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

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

Уравнение Шеннона может использовать:

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

Хартли понимал информационное получение как подбор одного вида данных из набора равновероятного сообщения и определил объём, содержащейся ВС, как логарифм N. Выполняются примеры решения по формуле Хартли в информатике: N = mn.

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

В этом случае средний объём информации, переносимой одним символом, можно считать расчётным: J (Z; Y) = Хапр (Z) — Хапест (Z) = Хапр (Y). Поскольку функция H (Y) = H (Z) и H (Y / Z) = 0, а индекс max = Hmax (Y) — максимальная энтропия источника класса сигнала, возникающая в результате распределения символов Y: p (y1) = p (y2) = … = p (ym) = 1 / My, т. е. Hmax (Y) = logaMy.

Следовательно, главная дискретная ширина полосы таблицы без информации о помехах в единицу времени равна: Cy = Vy • max = Vy • Hmax (Y) = Vy • logaMy или записываться Ck = Vk • logaMy. Где буква Mk — должно быть максимально возможное количество уровней, разрешённых для передачи по этому каналу (конечно, может обозначаться Mk = My).

Согласно теореме, метод кодирования онлайн, который может использоваться и позволяет:

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

Источник

Теорема Шеннона для канала без помех

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

Первая теорема Шеннона:если пропускная способность канала без помех превышает производительность источника сообщений, т.е. удовлетворяется условие C_k >V_u,

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

2. Теорема Шеннона для канала с помехами

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

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

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

Источник

Теорема Шеннона

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

Содержание

Утверждение теоремы

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

— пропускная способность канала, бит/с; — полоса пропускания канала, Гц; — полная мощность сигнала над полосой пропускания, Вт или В²; — полная шумовая мощность над полосой пропускания, Вт или В²; — частное от деления отношения сигнала к его шуму (SNR) на гауссовский шум, выраженное как отношение мощностей.

История развития

В течение конца 1920-х гг. Гарри Найквист и Ральф Хартли разработали фундаментальные идеи, связанные с передачей информации, с помощью телеграфа как системы коммуникаций. В то время, это был прорыв, но науки как таковой не существовало. В 1940-х гг., Клод Шеннон ввёл понятие пропускной способности канала, которое базировалось на идеях Найквиста и Хартли, а затем сформулировал полную теорию передачи информации.

Критерий Найквиста

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

где — частота импульса (имп/с), и — полоса пропускания (Гц).

Формула Хартли

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

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

Если скорость передачи сообщений меньше пропускной способности канала связи

то существуют коды и методы декодирования такие, что средняя и максимальная вероятности ошибки декодирования стремятся к нулю, когда длина блока стремится к бесконечности.

C,» border=»0″ />

то кода, на основе которого можно добиться сколько угодной малой вероятности возникновения ошибки, не существует.

Теорема Шеннона — Хартли

В данной теореме определено, что достичь максимальной скорости (бит/с) можно путем увеличения полосы пропускания и мощности сигнала и, в то же время, уменьшения шума.

Теорема Шеннона — Хартли ограничивает информационную скорость (бит/с) для заданной полосы пропускания и отношения «сигнал/шум». Для увеличения скорости необходимо увеличить уровень полезного сигнала, по отношению к уровню шума.

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

Удивительно, но не только ограничения полосы пропускания влияют на количество передаваемой информации. Если мы комбинируем шум и ограничения полосы пропускания, мы действительно видим, что есть предел количества информации, которую можно было передать, даже используя многоуровневые методы кодирования. В канале, который рассматривает теорема Шеннона — Хартли, шум и сигнал дополняют друг друга. Таким образом, приёмник воспринимает сигнал, который равен сумме сигналов, кодирующего нужную информацию и непрерывную случайную, которая представляет шум.

Это дополнение создает неуверенность относительно ценности оригинального сигнала. Если приёмник обладает информацией о вероятности ненужного сигнала, который создает шум, то можно восстановить информацию в оригинальном виде, рассматривая все возможные влияния шумового процесса. В случае теоремы Шеннона — Хартли шум, как таковой, произведен гауссовским процессом с некоторыми отклонениями в канале передачи. Такой канал называют совокупным белым гауссовским шумовым каналом, так как гауссовский шум является частью полезного сигнала. «Белый» подразумевает равное количество шума во всех частотах в пределах полосы пропускания канала. Такой шум может возникнуть при воздействии случайных источников энергии, а также быть связан с ошибками, возникшими при кодировании. Зная о вероятности возникновения гауссовского шума, значительно упрощается определение полезного сигнала.

Значение теоремы

Пропускная способность канала и формула Хартли

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

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

Источник