теория информации 2019. Файл от Енота. 1. Функциональная схема системы передачи информации, назначение ее составляющих
 Скачать 0.8 Mb.
|
|
1 1. Функциональная схема системы передачи информации, назначение ее составляющих Схема предстаалена следующим образом: Источник, кодирование (на стороне передатчика), канал (который может быть подвержен помехам), декодирование (на стороне приемника), получатель. Рисунок 1.1 – система передачи информации 2. Основные виды сигналов, используемых при передаче информации Рисунок 2.1 – виды сигналов Сигналы делятся на два типа: цифровой и аналоговый. Цифровой: сигнал, который можно представить в виде последовательности дискретных (цифровых) значений. (Цифровой сигнал представляется в виде нулей и единиц) Аналоговый: сигнал данных, у которого каждый из представленных параметров описывается функцией времени и непрерывным множеством возможных значений. 2 Рисунок 2.2 – примерный вид сигналов 3. Характеристики источника информации и канала связи Основными информационными характеристиками источника информации являются: 1. количество информации в сообщениях (информативность); 2. энтропия источника информации (энтропия); 3. избыточность источника информации (избыточность); 4. производительность источника сообщений (производительность). Основными информационными характеристиками канала являются: 1. скорость передачи информации по каналу связи (скорость); 2. пропускная способность канала связи (пропускная способность). 4. Энтропия источника дискретных сообщений Энтропия – среднее количество информации, которое приходится на одно сообщение (один символ последовательности), поступающее от источника без памяти. Получим, применяя операцию усреднения по всему объему алфавита 𝐻(𝐴) = − ∑ 𝑃(𝑎 𝑖 𝐾 𝑖=1 ) log 2 𝑃(𝑎 𝑖 ) = ∑ 𝑃(𝑎 𝑖 ) log 2 1 𝑃(𝑎 𝑖 ) 𝐾 𝑖=1 (4.1) (Уравнение 4.1) известно как формула Шеннона для энтропии источника дискретных сообщений. (ее высчитывали в ДЗ №1) Энтропия равна нулю, если с вероятностью 100% (1.0) источником выдается всегда одно и то же сообщение (в этом случае неопределенность в поведении источника сообщений отсутствует). Энтропия максимальна, если символы источника появляются независимо и с одинаковой вероятностью. 5. Энтропия источника непрерывных сообщений 3 Полная энтропия источника непрерывных сообщений состоит из двух слагаемых, одно из которых определяется законом распределения, а второе является постоянной величиной, определяющей шаг квантования, который влияет на точность измерений. Этот член выражения определяет постоянную составляющую и исключается из рассмотрения. 6. Энтропия сложных сообщений и ее свойства * В понимании энтропии сложных сообщений, необходимо выделить 4 свойства: 1. Энтропия источника и количество информации тем больше, чем больше размер алфавита источника; 2. Энтропия источника зависит от статистических свойств сообщений. Энтропия максимальна, если сообщения источника равновероятны и статистически независимы; 3. Энтропия источника, вырабатывающего неравновероятные сообщения, всегда меньше максимально достижимой; 4. При наличии статистических связей между элементарными сообщениями (памяти источника) его энтропия уменьшается. А также в этот раздел входит все то, что входит в п.4 и 5 данной работы. https://studizba.com/files/show/doc/129245-1-63429.html 7. Количество информации в сообщении при недостоверной передаче * Если принятое сообщение недостоверно, то количество получаемой приемником информации уменьшается на величину неопределенности, вносимой помехами. Если неопределенность источника информации не превышает пропускной способности канала, то существует код, обеспечивающий передачу информации через канал с помехами со сколь угодно малой частотой 4 ошибок. Такие коды можно получить, вводя избыточность в передаваемую информацию, что потребует дополнительных разрядов в коде сообщения. В вычислительной технике для передачи информации широко применяются посылочные корректирующие коды, имеющие дополнительные контрольные разряды. Эти коды имеют различную степень избыточности, от которой и зависит их корректирующая способность. Чтобы можно было не только обнаружить ошибку, возникшую при передаче данных, но и исправить ее, необходимо использовать коды с большей избыточностью (с большим количеством дополнительных разрядов). Примером может служить метод Р. Хэмминга, пользуясь которым можно построить коды различной длины. Эти коды позволяют исправлять все одиночные ошибки, а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки, но не исправлять их. Рисунок 7.1 – Код Хэмминга 8. Энтропия и количество информации при статистической зависимости элементов сообщений * Сообщение может состоять из отдельных элементов (слов, букв, цифр и т.п.), каждый из которых можно рассматривать как сообщение более низкого ранга. В этом случае сообщение следует рассматривать как сложное, и его 5 энтропия определяется энтропией элементов, их вероятностными характеристиками и статистическими свойствами (степенью зависимости). Сообщение, в котором элементы некоррелированы (статистически не зависимы) и равновероятны, обладает максимальной энтропией (2.12) , (2.15) Hmax (x) . В противном случае энтропия сообщения уменьшается. Сообщения, энтропия которых максимальна, являются оптимальными с точки зрения наибольшего количества передаваемой информации. Мерой количественной оценки того, насколько данное реальное сообщение по своей энтропии отличается от соответствующего ему оптимального сообщения: является коэффициент сжатия 𝜌 = 𝐻(𝑥) 𝐻 𝑚𝑎𝑥 (𝑥) (8.1) Если передается последовательность сообщений, то справедливо равенство 𝑛 ∗ 𝐻(𝑥) = 𝑛 ′ 𝐻 𝑚𝑎𝑥 (𝑥) (8.2) где n и nç длина последовательностей реальных и оптимальных сообщений. Тогда коэффициент сжатия можно выразить через длины последовательностей 𝜌 = 𝐻(𝑥) 𝐻 𝑚𝑎𝑥 (𝑥) = 𝑛 ′ 𝑛 (8.3) Таким образом, реальные сообщения при одинаковой информативности обладают определенной избыточностью (длиннее) по сравнению с оптимальными. Мерой избыточности является коэффициент избыточности 𝑟 = 𝑛−𝑛 ′ 𝑛 = 1 − 𝜌 = 𝐻 𝑚𝑎𝑥 (𝑥)−𝐻 (𝑥) 𝐻 𝑚𝑎𝑥 (𝑥) (8.4) Избыточность приводит к увеличению времени передачи сообщений, излишней загрузке каналов связи. Однако избыточность повышает помехоустойчивость сообщений. Все языки обладают избыточностью, что позволяет восстановить слова и даже целые фразы при наличии ошибок. Наконец, сообщения могут формироваться источником с большим или меньшим темпом. 6 В этой связи вводится еще одна характеристика - производительность источника, которая характеризуется величиной энтропии, формируемой источником в единицу времени R = 𝐻(𝑥) 𝑇 (8.5) где H(x) - величина энтропии, формируемой источником за время Т. 9. Эффективное кодирование (алгоритм Шеннона) 1. Символы первичного алфавита m 1 выписывают по убыванию вероятностей; 2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу; 3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1»; 4. Полученные части рекурсивно делятся, и их частям назначаются соответствующие двоичные цифры в префиксном коде. Рисунок 9.1 - алгоритм шеннона (пример таблица) Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей может быть одинакова для двух вариантов разделения 7 (учитывая, что все символы первичного алфавита имеют вероятность больше нуля). Рисунок 9.2 – кодирование по алгоритму Шеннона http://toi.kb-8.com/task?n=3 10. Эффективное кодирование (алгоритм Фано (Шеннона - Фано)) 1. на вход приходят упорядоченные по невозрастанию частот данные; 2. находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева; 3. шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок. 8 Рисунок 10.1 – кодирование алгоритмом Шеннона-Фано, этап: 1 Рисунок 10.2 – кодирование алгоритмом Шеннона-Фано, этап: 2 9 Рисунок 10.3 – кодирование алгоритмом Шеннона-Фано, этап: 3 Рисунок 10.4 – кодирование алгоритмом Шеннона-Фано, этап: 4 10 Рисунок 10.5 – кодирование алгоритмом Шеннона-Фано, этап: 5 Рисунок 10.6 – кодирование алгоритмом Шеннона-Фано, этап: 6 http://toi.kb-8.com/task?n=3 11. Эффективное кодирование (алгоритм Хаффмана) 1. на вход приходят упорядоченные по невозрастанию частот данны; 2. выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»); 3. потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0»; 11 4. шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень». http://toi.kb-8.com/huffman http://toi.kb-8.com/task?n=3 12. Арифметическое кодирование * Арифметическое кодирование — один из алгоритмов энтропийного сжатия. В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1. Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу. Рисунок 12.1 – арифметическое кодирование Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту 12 операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока. 13. Универсальное кодирование. Коды Элиаса Универсальный код – префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение – монотонно (то есть p (i) ≥ p (i+1) для любого i ), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей Универсальное кодирование применяется, когда декодеру приходится работать с данными по мере поступления. Большинство префиксных кодов для целых чисел назначает более длинные ключевые слова большим целым числам. Такой код используется, чтобы эффективно закодировать потоковое сообщение из набора возможных кодовых слов, методом упорядочивания набор кодовых слов по уменьшению вероятности, а затем пересылая индекс слова. Универсальные коды в общем не используются для точно известных распределений вероятностей. Универсальные коды включают в себя: – Унарное кодирование; – Гамма-код Элиаса; – Дельта-код Элиаса; – Омега-код Элиаса; – Дельта-код; – Кодирование Фибоначчи; – Экспоненциальный код Голомба. Гамма-код Элиаса Универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он используется при 13 кодировании целых чисел, максимальное значение которых не может быть определено заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто, чем большие. (Листинг кода находится в приложении А) Дельта-код Элиаса Универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Дельта-код с некоторого числа короче гамма-кода. (Листинг кода находится в приложении А) Омега-код Элиаса – это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. В отличие от двух других кодов, омега- код рекурсивно кодирует префикс, именно поэтому он также известен, как рекурсивный код Элиаса. (Листинг кода находится в приложении А) 14. Словарные методы кодирования. Алгоритм LZW Алгоритм LZW 1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения; 2. Считать очередной символ K из кодируемого сообщения; 3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, закончить кодирование, иначе переход к 4; 4. Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к шагу 2, иначе выдать код, соответствующий ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к шагу 2. LZW — алгоритм сжатия на основе "словаря". Это означает, что вместо сведения в таблицу количества символов и построения деревьев (как при кодировании по Хаффману), LZW кодирует данные, обращаясь к словарю. Таким образом, чтобы закодировать подстроку, в выходной файл нужно записать только одно кодовое число, соответствующее индексу этой подстроки в словаре. Хотя LZW часто рассматривается в контексте сжатия 14 текстовых файлов, его можно использовать для любого типа файлов. Однако, как правило, он лучше всего справляется с файлами, где есть повторяющиеся подстроки, например, с текстовыми файлами. 15. Дискретный симметричный канал без памяти * ДСК является частным случаем более общего канала с дискретным входом и дискретным выходом. Предположим, что входом кодера канала являются q-ичные символы, т.е.X = {x 0 , x 1 , … , x 𝑞−1 }, а выходом детектора являются Q-ичные символы, где 𝑄 ≥ 𝑀 = 2 𝑞 . Если канал и модуляция без памяти, тогда характеристика вход-выход составного канала 16. Дискретный симметричный канал с памятью * Для дискретного канала с памятью каждая буква выходной последовательности статистически зависит как от соответствующего входа, так и от прошлых входов и выходов (здесь и в дальнейшем предполагается, что канал является каналом без предвосхищения, т. е. при заданном текущем входе и заданных входах и выходах в прошлом текущий выход статистически не зависит от будущих входов). Без потери общности последовательность входов и выходов вплоть до заданного момента может быть рассмотрена как состояние канала в этот момент. В этих понятиях статистическое поведение канала описывается совместной вероятностной мерой на выходной букве и состоянии в заданный момент при условии, что заданы текущая входная буква и предыдущее состояние. 17. Основные определения и классификация помехоустойчивых кодов. Помехоустойчивые коды делятся на блочные и непрерывные. Блочными называются коды, в которых последовательность информационных символов разбивается на группы и каждая из них преобразуется в определённую последовательность (блок) кодовых символов. 15 В блочных кодах кодирование (формирование проверочных символов) и декодирование (обнаружение и исправление ошибок) выполняются в пределах каждой кодовой комбинации (блока) в отдельности по соответствующим алгоритмам. Непрерывные или рекуррентные коды образуют последовательность символов, не разделяемую на отдельные кодовые комбинации. Кодирование и декодирование непрерывно совершаются над последовательностью символов без деления их на блоки. Формирование проверочных символов ведётся по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными или цепными. 18. Структура и матричное описание блоковых кодов * https://studfile.net/preview/1757715/page:3/ https://studme.org/109992/informatika/porozhdayuschie_matritsy_blochnyh _kodov 19. Связь корректирующей способности с кодовым расстоянием Степень отличия любых двух кодовых комбинаций характеризуется расстоянием между ними в смысле Хэмминга или просто кодовым расстоянием. Оно выражается числом символов, в которых комбинации отличаются одна от другой. Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2. Например: Рисунок 19.1 – пример получения кодового расстояния 16 Минимальное расстояние, взятое по всем парам разрешенных комбинаций кода, называют минимальным кодовым расстоянием. Код обнаруживает одиночные ошибки, а также другие ошибки нечетной кратности. 20. Кодирование Хэмминга Код Хэмминга — самоконтролирующийся и самокорректирующийся код. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите слова) и находить двойную. Назван в честь американского математика Ричарда Хэмминга, предложившего код. Систематические коды образуют большую группу из блочных, разделимых кодов (в которых все символы слова можно разделить на проверочные и информационные). Особенностью систематических кодов является то, что проверочные символы образуются в результате линейных логических операций над информационными символами. Кроме того, любая разрешенная кодовая комбинация может быть получена в результате линейных операций над набором линейно независимых кодовых комбинаций. Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. 21. Общие принципы построения циклических кодов * Построение циклического кода производится, исходя из разрядности m исходного кода и требуемой от циклического кода корректирующей способности, задаваемой в виде числа обнаруживаемых r и числа исправляемых s ошибок. По сути дела, построение кода сводится к выбору образующего полинома P(x) и составлению образующей матрицы. Корректирующая способность зависит от кодового расстояния d. Под кодовым расстоянием между двумя комбинациями F1 и F2 понимают число разрядов, в которых эти комбинации отличаются друг от друга. Кодовое расстояние равно 17 числу единиц (весу) W в сумме двух комбинаций по модулю 2, т.е. d WF F = ⊕ ( ) 1 2 . Рисунок 21.1 – слайд с информацией о циклических кодах 22. Алгоритмы декодирования циклических кодов * Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования, использует два способа: - при кодировании "классическим" способом декодирование основано на использовании свойства делимости без остатка кодового многочлена u(x) циклического (n,k)-кода на порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя деление принятого кодового слова, описываемого многочленом на g(x), вычисление и анализ остатка r(x). Если r(x)=0, то принятое кодовое слово считается неискаженным. Если r(x)№0, то принятое кодовое слово стирается и формируется сигнал "ошибка". - при кодировании способом МККТТ декодирование основано на свойстве получения определенного контрольного остатка R 0 (x) при делении принятого кодового многочлена u(x) на порождающий многочлен. Поэтому, если полученный при делении остаток , то принятое кодовое слово 18 считается неискаженным. Если остаток , то принятое кодовое слово стирается и формируется сигнал "ошибка". Рисунок 22.1 – слайд с информацией о циклических кодах 23. Принципы построения кодов БЧХ Теоретически коды БЧХ могут исправлять произвольное количество ошибок, но при этом существенно увеличивается длительность кодовой комбинации, что приводит к уменьшению скорости передачи данных и усложнению приемо-передающей аппаратуры (схем кодеров и декодеров). Методика построения кодов БЧХ отличается от обычных циклических, в основном, выбором определяющего полинома P(х). Коды БЧХ строятся по заданной длине кодового слова n и числа исправляемых ошибок S , при этом количество информационных разрядов k не известно пока не выбран определяющий полином. 24. Алгоритмы декодирования кодов БЧХ Основным алгоритмом декодирования кодов БЧХ является так называемый алгебраический или синдромный метод декодирования. Принципом, лежащим в основе этого метода, является использование 19 элементов поля Галуа для нумерации позиций элементов принятого кодового слова r(x) 25. Способы задания и характеристики сверточных кодов * Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными примерами их эффективного применения являются системы связи, системы мобильной связи, модемы для телефонных каналов. Формально сверточный код — это корректирующий ошибки код, в котором: 1. на каждом такте работы кодера k символов входной полубесконечной последовательности преобразуются в n > k символов выходной последовательности 2. в преобразовании также участвуют m предыдущих символов 3. выполняется свойство линейности (если двум кодируемым последовательностям x и y соответствуют кодовые последовательности X и Y, то кодируемой последовательности ax + by соответствует aX + bY. Свёрточный код является частным случаем древовидных и решетчатых кодов. Рисунок 25.1 – решение задачи по сверочным кодом с помощью схемы 20 26. Декодирование сверточных кодов по алгоритму Витерби * Декодер Витерби реализует метод максимального правдоподобия в несколько ином смысле, но очень близком к классическому. В наиболее распространенном варианте применения ВД находит кодовую последовательность, ближайшую к принятой, обрабатывая ее бит за битом Вместо подсчета веса каждой из возможных кодовых последовательностей декодер Витерби прослеживает состояния решетки и проходящие через них пути. 21 ПРИЛОЖЕНИЕ А def GammaEnc(n): answer = [] k = str(DTB(n)) l = len(str(k)) - 1 res = "" for i in range(0, l, 1): res += "0" res += k answer.append("Кодирование с помощью гамма-кода") answer.append(f"1. Записать число в двоичном представлении: {k}") answer.append( f"2. Перед двоичным представлением дописать нули, количество нулей на единицу меньше количества битов двоичного представления числа: {res}") answer.append(f"{res}") return answer def GammaDec(n): answer = [] s = 0 for i in range(0, len(n), 1): if str(n)[i] == "0": s += 1 else: break res = BTD(str(n)[s:len(n)]) answer.append("Декодирование с помощью гамма-кода") answer.append(f"1. Считать все нули, встречающиеся до первой 1, всего их: {s}") answer.append( f"2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением 2^N, считать оставшиеся N цифр целого числа и перевести в десятичное представление: {res}") answer.append(f"{res}") return answer def DeltaEnc(n): answer = [] 22 L = len(str(DTB(n))) M = len(str(DTB(L))) S1 = "" for i in range(0, M - 1, 1): S1 += "0" S1 += "1" L2 = str(DTB(L)) Ll = 0 for i in range(0, len(L2), 1): if str(L2)[i] == "1": Ll += 1 break else: break L2 = str(L2)[Ll:len(L2)] M2 = str(DTB(n)) Ml = 0 for i in range(0, len(M2), 1): if str(M2)[i] == "1": Ml += 1 break else: break M2 = str(M2)[Ml:len(M2)] S2 = S1 + str(L2) S3 = S2 + str(M2) answer.append("Кодирование с помощью дельта-кода") answer.append(f"1. Сосчитать L — количество значащих битов в двоичном представлении числа N: L = {L}") answer.append(f"2. Сосчитать M — количество значащих битов в двоичном представлении числа L: M = {M}") answer.append(f"3. Записать M — 1 нулей и одну единицу: {S1}") answer.append(f"4. С правой стороны дописать биты числа L без старшей единицы: {S2}") answer.append(f"5. С правой стороны дописать биты числа N без старшей единицы (N2): {S3}") answer.append(f"{S3}") return answer def DeltaDec(n): 23 answer = [] M = 0 for i in range(0, len(n), 1): if str(n)[i] == "0": M += 1 else: break n = str(n)[M + 1:len(n)] r = pow(2, M) + BTD(n[0:2]) nn = str(n)[M:len(n)] rr = pow(2, r - 1) + BTD(nn) answer.append("Декодирование с помощью дельта-кода") answer.append(f"1. Считаем количество нулей до первой единицы во входном потоке: M = {M}") answer.append(f"2. Читаем из потока следующие M бит ({n[0:2]}). Это дает нам L=2^M + {n[0:2]} = {r}") answer.append(f"3. Прочитать из потока следующие L-1 = {r - 1} бита ({nn}), это даёт N=2^(L-1) + {nn} = {rr}") answer.append(f"{rr}") return answer def OmegaEnc(n): answer = [] k = "0" answer.append("Кодирование с помощью омега-кода") answer.append(f"1. Записываем 0: {k}") N = n answer.append(f"2. N = {N}") while int(N) > 1: k = str(DTB(N)) + k answer.append(f"3. Добавляем справа от нуля двоичное представление N: {k}") N = len(str(DTB(N))) - 1 answer.append(f"2. N = {N}") answer.append(k) return answer def OmegaDec(n): 24 answer = [] k = "1" answer.append("Декодирование с помощью омега-кода") answer.append(f"1. Записываем 1: {k}") N = 1 while n[0] == "1": N = N + 1 k = n[0:N] n = n[N:len(n)] answer.append(f"2. Считываем группу {k}, N = {BTD(k)}") N = BTD(k) answer.append(N) return answer |