Общая условная энтропия
Рассмотрение понятия условной энтропии в теории информации. Определение избыточности сообщений. Построение оптимальных кодов при помощи методик Шенона-Хано и Хаффмена. Обнаружение и исправление ошибок в сообщениях. Описание методов сжатия информации.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курс лекций |
Язык | русский |
Дата добавления | 18.02.2013 |
Размер файла | 533,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Пример: Исходная кодовая комбинация - 0101111000, принятая - 0001011001 (т. е. произошел тройной сбой). Показать процесс обнаружения ошибки, если известно, что комбинации кода были образованы при помощи многочлена 101111.
Решение:
Остаток не нулевой, комбинация бракуется. Указать ошибочные разряды при трехкратных искажениях такие коды не могут.
III. Циклические коды, исправляющие две и большее количество ошибок,
Методика построения циклических кодов с отличается от методики построения циклических кодов с только в выборе образующего многочлена. В литературе эти коды известны как коды БЧХ (первые буквы фамилий Боуз, Чоудхури, Хоквинхем - авторов методики построения циклических кодов с ).
Построение образующего многочлена зависит, в основном, от двух параметров: от длины кодового слова п. и от числа исправляемых ошибок s. Остальные параметры, участвующие в построении образующего многочлена, в зависимости от заданных и могут быть определены при помощи таблиц и вспомогательных соотношений, о которых будет сказано ниже.
Для исправления числа ошибок еще не достаточно условия, чтобы между комбинациями кода минимальное кодовое расстояние . необходимо также, чтобы длина кода удовлетворяла условию
(79)
при этом п всегда будет нечетным числом. Величина h определяет выбор числа контрольных символов и связана с и s следующим соотношением:
(80)
С другой стороны, число контрольных символов определяется образующим многочленом и равно его степени. При больших значениях h длина кода п становится очень большой, что вызывает вполне определенные трудности при технической реализации кодирующих и декодирующих устройств. При этом часть информационных разрядов порой остается неиспользованной. В таких случаях для определения h удобно пользоваться выражением
(81)
где является одним из сомножителей, на которые разлагается число п.
Соотношения между , С и h могут быть сведены в следующую таблицу
№ п/п |
h |
C |
||
1 2 3 4 5 6 7 8 9 10 |
3 4 5 6 7 8 9 10 11 12 |
7 15 31 63 127 255 511 1023 2047 4095 |
1 5; 3 1 7; 3; 3 1 17; 5; 3 7; 3; 7 31; 11; 3 89; 23 3; 3; 5; 7; 13 |
Например, при h = 10 длина кодовой комбинации может быть равна и 1023 и 341 (С = 3), и 33 (С =31), и 31 (С = 33), понятно, что п не может быть меньше Величина С влияет на выбор порядковых номеров минимальных многочленов, так как индексы первоначально выбранных многочленов умножаются на С.
Построение образующего многочлена производится при помощи так называемых минимальных многочленов , которые являются простыми неприводимыми многочленами (см. табл. 2, приложение 9). Образующий многочлен представляет собой произведение нечетных минимальных многочленов и является их наименьшим общим кратным (НОК). Максимальный порядок определяет номер последнего из выбираемых табличных минимальных многочленов
(82)
Порядок многочлена используется при определении числа сомножителей . Например, если s = 6, то . Так как для построения используются только нечетные многочлены, то ими будут: старший из них имеет порядок .
Как видим, число сомножителей равно 6, т. е. числу исправляемых ошибок.
Таким образом, число минимальных многочленов, участвующих в построении образующего многочлена,
(83)
а старшая степень
(84)
( указывает колонку в таблице минимальных многочленов, из которой обычно выбирается многочлен для построения ).
Степень образующего многочлена, полученного в результате перемножения выбранных минимальных многочленов,
(85)
В общем виде
(86)
Декодирование кодов БЧХ производится по той же методике, что и декодирование циклических кодов с . Однако в связи с тем, что практически все коды БЧХ представлены комбинациями с , могут возникнуть весьма сложные варианты, когда для обнаружения и исправления ошибок необходимо производить большое число циклических сдвигов. В этом случае для облегчения можно комбинацию, полученную после -кратного сдвига и суммирования с остатком, сдвигать не вправо, а влево на циклических сдвигов. Это целесообразно делать только при .
СЖАТИЕ ИНФОРМАЦИИ
Сжатие информации представляет собой операцию, в результате которой данному коду или сообщению ставится в соответствие более короткий код или сообщение.
Сжатие информации имеет целью - ускорение и удешевление процессов механизированной обработки, хранения и поиска информации, экономия памяти ЭВМ. При сжатии следует стремиться к минимальной неоднозначности сжатых кодов при максимальной простоте алгоритма сжатия. Рассмотрим наиболее характерные методы сжатия информации.
Сжатие информации делением кода на части, меньшие некоторой наперед заданной величины А, заключается в том, что исходный код делится на части, меньшие А, после чего полученные части кода складываются между собой либо по правилам .двоичной арифметики, либо по модулю 2. Например, исходный код 101011010110; A = 4
Сжатие информации с побуквенным сдвигом в каждом разряде [5], как и предыдущий способ, не предусматривает восстановления сжимаемых кодов, а применяется лишь для сокращения адреса либо самого кода сжимаемого слова в памяти ЭВМ.
Предположим, исходное слово "газета" кодируется кодом, в котором длина кодовой комбинации буквы l = 8:
Г - 01000111; а - 11110000; з - 01100011; е - 00010111; т - 11011000.
Полный код слова "Газета"
010001111111000001100011000101111101100011110000.
Сжатие осуществляется сложением по модулю 2 двоичных кодов букв сжимаемого слова с побуквенным сдвигом в каждом разряде.
Допустимое количество разрядов сжатого кода является вполне определенной величиной, зависящей от способа кодирования и от емкости ЗУ. Количество адресов, а соответственно максимальное количество слов в выделенном участке памяти машины определяется из следующего соотношения
(88)
где - максимально допустимая длина (количество двоичных разрядов) сжатого кода; N - возможное количество адресов в ЗУ. Если представить процесс побуквенного сдвига в общем виде, как показано на рис. 1, а, то длина сжатого кода
где k - число побуквенных сдвигов; - длина кодовой комбинации буквы.
Так как сдвигаются все буквы, кроме первой, то и число сдвигов , где L - число букв в слове. Тогда
В русском языке наиболее длинные слова имеют 23 - 25 букв. Если принять , с условием осуществления побуквенного сдвига с каждым шагом ровно на один разряд, для n и l могут быть получены следующие соотношения
Если значение не удовлетворяет неравенству (88), можно конечные буквы слова складывать по модулю 2 без сдвига относительно предыдущей буквы, как это показано на рис 1, б.
Например, если для предыдущего примера со словом "Газета" , сжатый код будет иметь вид:
Метод сжатия информации на основе исключения повторения в старших разрядах последующих строк, массивов одинаковых элементов старших разрядов предыдущих строк массивов основан на том, что в сжатых массивах повторяющиеся элементы старших разрядов заменяются некоторым условным символом.
Очень часто обрабатываемая информация бывает представлена в виде набора однородных массивов, в которых элементы столбцов или строк массивов расположены в нарастающем порядке. Если считать старшими разряды, расположенные левее данного элемента, а младшими - расположенные правее, то можно заметить, что во многих случаях строки матриц отличаются друг от друга в младших разрядах. Если при записи каждого последующего элемента массива отбрасывать все повторяющиеся в предыдущем элементы, например в строке стоящие подряд элементы старших разрядов, то массивы могут быть сокращены от 2 до 10 и более разрядов [2].
Для учета выброшенных разрядов вводится знак раздела , который позволяет отделить элементы в свернутом массиве. В случае полного повторения строк записывается соответствующе количество . При развертывании вместо знака восстанавливаются все пропущенные разряды, которые были до элемента, стоящего непосредственно за в сжатом тексте.
Для примера рассмотрим следующий массив:
Свернутый массив будет иметь вид:
Расшифровка (развертывание) происходит с конца массива. Переход на следующую строку происходит по двум условиям: либо по заполнению строки, либо при встрече .
Пропущенные цифры заполняются автоматически по аналогичным разрядам предыдущей строки. Заполнение производится с начала массива. Этот метод можно развить и для свертывания массивов, в которых повторяющиеся разряды встречаются не только с начала строки. Если в строке один повторяющийся участок, то кроме добавляется еще один дополнительный символ К, означающий конец строки. Расшифровка ведется от К до К. Длина строки известна. Нужно, чтобы оставшиеся между K цифры вместе с пропущенными разрядами составляли полную строку. При этом нам все равно, в каком месте строки выбрасываются повторяющиеся разряды, лишь бы в строке было не более одного участка с повторяющимися разрядами. Например:
Если в строке есть два повторяющихся участка, то, используя этот метод, выбрасываем больший.
Процесс развертывания массива осуществляется следующим образом: переход на следующую строку происходит при встрече К
Пропущенные цифры заполняются по аналогичным разрядам предыдущей строки начиная с конца массива.
Если в строке массива несколько повторяющихся участков, то можно вместо вставлять специальные символы, указывающие на необходимое число пропусков.
Например, если обозначить количество пропусков, соответственно, Х - 2; Y - 3; Z - 5, то исходный и свернутый массивы будут иметь вид:
Процесс развертывания массива осуществляется следующим образом: длина строки известна, количество пропусков определяется символами X, Y, Z
Пропущенные цифры заполняются по аналогичным разрядам предыдущей строки. Условием перехода на следующую строку является заполнение предыдущей строки.
Метод Г. В. Ливинского основан на том, что в памяти машины хранятся сжатые числа, разрядность которых меньше разрядности реальных чисел. Эффект сжатия достигается за счет того, что последовательности предварительно упорядоченных чисел разбиваются на ряд равных отрезков, внутри которых отсчет ведется не по их абсолютной величине, а от границы предыдущего отрезка. Разрядность чисел, получаемых таким образом, естественно, меньше разрядности соответствующих им реальных чисел [18, 21].
Для размещения в памяти ЭВМ М кодов, в которых наибольшее из кодируемых чисел равно N, необходим объем памяти
С ростом N длина кодовой комбинации будет расти как . Для экономии объема памяти Q, число , где выражение в скобках - округленное значение до ближайшего целого числа, разбивают на L равных частей. Максимальное число в полученном интервале чисел будет не больше . Величина определяет разрядность хранимых чисел, объем памяти для их хранения будет не больше . Если в памяти ЭВМ хранить адреса границ отрезков и порядковые номера хранимых чисел, отсчитываемых от очередной границы, то определяет разрядность чисел для выражения номера границы (в последнем интервале должно быть хотя бы одно число); объем памяти для хранения номеров границ будет где - число границ между отрезками (это число всегда на единицу меньше, чем число отрезков). Общий объем памяти при этом будет не больше
(89)
Чтобы найти, при каких L выражение (89) принимает минимальное значение, достаточно продифференцировать его по L и, приравнять производную к нулю. Нетрудно убедиться, что будет при
(90)
Если подставить значение в выражение (89), то получим. значение объема памяти при оптимальном количестве зон, на, которые разбиваются хранимые в памяти ЭВМ числа,
(91)
Для значений при вычислениях можно пользоваться приближенной формулой
(92)
При поиске информации в памяти ЭВМ прежде всего определяют значение и находят величину интервала между двумя границами
Затем определяют, в каком именно из интервалов находится искомое число х
После этого определяется адрес искомого числа как разность между абсолютным значением числа и числом, которое является граничным для данного интервала.
Размещено на Allbest.ru
...Подобные документы
Механизм передачи информации, ее количество и критерии измерения. Единицы информации в зависимости от основания логарифма. Основные свойства и характеристики количества информации, ее энтропия. Определение энтропии, избыточности информационных сообщений.
реферат [33,9 K], добавлен 10.08.2009Задачи и постулаты прикладной теории информации. Разновидности помехоустойчивых кодов. Кодирование информации для канала с помехами. Энтропия при непрерывном сообщении. Количественная оценка информации. Условная и взаимная энтропия и ее свойства.
курс лекций [3,2 M], добавлен 28.04.2009Количество информации и ее мера. Определение количества информации, содержащегося в сообщении из ансамбля сообщений источника. Свойства количества информации и энтропии сообщений. Избыточность, информационная характеристика источника дискретных сообщений.
реферат [41,4 K], добавлен 08.08.2009Способы передачи и хранения информации наиболее надежными и экономными методами. Связь между вероятностью и информацией. Понятие меры количества информации. Энтропия и ее свойства. Формула для вычисления энтропии. Среднее количество информации.
реферат [99,7 K], добавлен 19.08.2015Общая характеристика информационных систем, предназначенных для передачи, преобразования и хранения информации. Изучение форм представления детерминированных сигналов. Энтропия сложных сообщений. Рассмотрение основных элементов вычислительных машин.
лекция [1,5 M], добавлен 13.04.2014Методы компрессии информации. Обзор и характеристика существующих методов сжатия информации, основанных на процедуре кодирования Хаффмена. Алгоритмы динамического кодирования методом FGK и Виттера. Программная реализация и руководство пользователя.
курсовая работа [33,2 K], добавлен 09.03.2009Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.
курсовая работа [325,1 K], добавлен 28.07.2009Объединение как совокупность нескольких ансамблей дискретных, случайных событий. Безусловная энтропия - среднее количество информации, приходящееся на один символ. Описание информационных свойств непрерывного источника. Понятие дифференциальной энтропии.
контрольная работа [106,8 K], добавлен 28.07.2009Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.
контрольная работа [491,4 K], добавлен 15.10.2013Основные положения теории защиты информации. Сущность основных методов и средств защиты информации в сетях. Общая характеристика деятельности и корпоративной сети предприятия "Вестел", анализ его методик защиты информации в телекоммуникационных сетях.
дипломная работа [1,1 M], добавлен 30.08.2010Задачи обработки и хранения информации при помощи ЭВМ. Сжатие и кодирование информации в информационно-вычислительных комплексах. Метод Лавинского как простейший метод сжатия информации (числовых массивов) путем уменьшения разрядности исходного числа.
курсовая работа [66,0 K], добавлен 09.03.2009Предмет и задачи теории информации, ее функции при создании АСУ. Определение пропускной способности дискретных (цифровых) каналов при отсутствии шумов. Расчет скорости передачи информации. Вычисление значения энтропии - среднего количества информации.
контрольная работа [112,0 K], добавлен 18.01.2015Основы теории передачи информации. Экспериментальное изучение количественных аспектов информации. Количество информации по Хартли и К. Шеннону. Частотные характеристики текстовых сообщений. Количество информации как мера снятой неопределенности.
лабораторная работа [42,3 K], добавлен 15.02.2011Оптимальное статистическое (экономное) кодирование. Основные понятия и определения теории кодирования. Принципы построения оптимальных кодов. Способность системы осуществлять прием информации в условиях наличия помех. Увеличение мощности сигналов.
реферат [69,3 K], добавлен 09.07.2009Помехоустойчивое кодирование, правильность передачи информации. Устранение ошибок в симплексных каналах связи с помощью корректирующих кодов. Способы обнаружения ошибок - контрольное суммирование, проверка на нечетность. Применение циклических кодов.
реферат [28,1 K], добавлен 03.08.2009Методы обеспечения целостности информации в системах стационарных и подвижных объектов. Определение оптимальных характеристик корректирующего кода, разработка кодирующего устройства; технические системы сбора телеметрической информации и охраны объектов.
дипломная работа [3,8 M], добавлен 01.07.2011Источники сообщений, сигналы и коды, примеры применения знания основ теории информации для практических целей. Расчет информационных характеристик и согласование дискретного источника с дискретным каналом без шума и с шумом, эффективное кодирование.
курсовая работа [179,6 K], добавлен 13.11.2009Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано.
курсовая работа [59,4 K], добавлен 17.04.2009Изучение сущности циклических кодов - семейства помехоустойчивых кодов, включающих в себя одну из разновидностей кодов Хэмминга. Основные понятия и определения. Методы построения порождающей матрицы циклического кода. Понятие открытой системы. Модель OSI.
контрольная работа [99,5 K], добавлен 25.01.2011Коды Боуза-Чоудхури-Хоквингема как широкий класс циклических кодов, применяемых для защиты информации от ошибок. Особенности коаксиальных магистральных кабелей КМ-4, основное назначение. Способы моделирования передачи информации по кабельной линии связи.
курсовая работа [1,7 M], добавлен 07.01.2013