Минимизация распространения ошибок при неравномерном кодировании символов сообщений тема диссертации и автореферата по ВАК РФ 05.12.04, кандидат технических наук Нго Биссе Жаки Терез

• Нго Биссе Жаки Терез
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Нго Биссе Жаки Терез

Введение.

Глава 1. Обобщенная классификация кодов.

1.1. Основные положения теории кодирования.

1.2. Классификация кодов по назначению.

1.2.1. Извлечение информации.

1.2.2. Хранение и передача информации.

1.2.3. Коды для предотвращения несанкционированного доступа.

1.2.4. Классификация кодов по области применения.

1.3. Классификация кодов по критерию обнаружения и исправления ошибок.

1.3.1. Общие сведения о дискретных кодах.

1.3.2. Блочные коды.

1.3.3. Непрерывные коды.

1.4. Классификация кодов по критерию числа элементов и длительности.

Выводы.

Глава 2. Анализ методов кодирования источника информации.

2.1. Избыточность дискретных источников.

2.2. Количество информации, содержащейся в текстовых сообщениях.

2.3. Статистика попарной корреляции букв французского и русского текстов.

2.4. Синтез алгоритма и программы обработки текста.

2.5. Расчет вероятности и информативность попарных элементов сообщений в тексте.

2.5.1. Французский текст.

2.5.2. Русский текст.

2.6. Частота попарной корреляции букв при большом объеме текста.

Выводы.

Глава 3. Разработка нового метода кодирования источника.

3.1.0 распространении ошибок неравномерных кодов.

3.2. Эффективное кодирование источника.

3.3. Код "Симоновича".

3.4. Синхронизация при наличии шума.

3.5. Эффективный метод кодирования источника.

3.6. Синтез алгоритма кода.

3.7. Сравнение предлагаемого кода с "кодом Симоновича", дополненных корректирующими символами по методу Хеммин

Выводы.

Глава 4. Разработка устройства, декодирующего предлагаемый код

4.1. Описание структурной схемы устройства, декодирующего предложенную.

4.2. Синтез регистра сдвига, счетчика, обнаружителей нулевого состояние счетчика и префикса кодового слова.

4.3. Декодеры информационной части кода.

4.4. Синтез приоритетного шифратора номера символов.

4.5. Определитель длины кодового слова.

Выводы.

Введение диссертации (часть автореферата) на тему «Минимизация распространения ошибок при неравномерном кодировании символов сообщений»

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

Для устранения избыточности первым эффективным статистическим кодом для источника был код, созданный С. Морзе в 1837 году [41]. Принцип его построения основан на том, что часто встречающимся буквам алфавита источника были поставлены в соответствие короткие кодовые слова, а редким — более длинные. За счет этого средняя длина кодового слова получается короче, чем при равномерном кодировании. С развитием теории информации, появились коды К. Шеннона, Р. Фано [39, 45], Д.А. Хаффмена [42], А. Лемпеля, Д. Зива, Р. Кричевского [14, 15, 71, 72] и др. Некоторые, как и код Морзе, строятся для заранее известной статистики источника, поэтому получили название статистических. В коде Морзе, каждая кодовая комбинация должна отделяться от другой специальным разделительным знаком. Таким знаком служит пауза, соответствующая по длительности тире (т.е. тройной длительности точки). В отличие от кода Морзе, в кодах Шеннона и Хаффме-на нет необходимости отделять друг от друга буквы (кодовые комбинации) специальным знаком, так как и без этого декодирование выполняется однозначно, и средняя длина кодовой комбинации намного уменьшается.

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

Источники информации делятся на непрерывные и дискретные. В диссертации рассматриваются только дискретные источники.

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

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

В связи с этим понятием, в 40-х годах XX века, К. Шеннон разработал математическую теорию, которая имеет дело к наиболее фундаментальными аспектами теории связи [45]. Заслуга Шеннона состоит в том, что различные виды информации, хотя они имеют различную природу, описываются одним числом - энтропией Н. f * •

ШУМ

Рис. В.1. Структурная схема канала извлечения, передачи и приема информации

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

Энтропия - мера неопределенности случайной ситуации. Смысл понятия энтропии заключается в следующем: если передается определенное сообщение, то тем самым получается некоторая информация об источнике, и неопределенность, заключенная в выборе сообщения для передачи, тем самым снимается. Таким образом, реализация любого сообщения заключается в снятии той неопределенности, которая предшествовала выбору этого сообщения. Чем больше была эта неопределенность, тем лучше должна оцениваться та информация, которая получается в результате ликвидации этой неопределенности. Поэтому считается, что количество информации, даваемое реализацией какого-либо сообщения, равно энтропии этого источника [20]. Энтропия равна нулю, если с вероятностью единица источником выдается всегда одно и то же сообщение (в этом случае неопределенность в поведении источника отсутствует). Можно сказать, что наиболее важной характеристикой дискретного источника сообщений является энтропия. Она показывает, насколько используются современные каналы связи и какие резервы заключены в передаваемых сообщениях для эффективности передачи.

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

Вся совокупность элементов х/, Х2, хз,.,хь.,хт называется алфавитом источника. Все, что ещё кроме алфавита известно для данного источника, это распределение вероятностей появления отдельных символов алфавита Р и Р2, Pj,.,Pi,.,Pm. Всякий ансамбль сообщений описывается некоторой неопределенностью. Степень этой неопределенности для различных источников разная, она тем большая, чем более равномерным является распределение вероятностей символов алфавита этого источника. Эта степень реализации любого сообщения из данного источника удобным образом описывается энтропией как: т н = -If£ fiiog^, (B.I) i где п — число символов (длина) сообщения.

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

Если рассматривать случаи оптимального использования каналов с поЛ мехами путем надлежащего кодирования, то можно ожидать, что при передаче сообщений по каналам связи, работающих с ошибками, достижение передачи с достаточно малой ошибкой связано с уменьшением скорости передачи. В действительности, как показал Шеннон, пропускная способность каналов имеет вполне определенное значение даже при сколь угодно малой частоте ошибок. В теории Шеннона приводятся 2 основные теоремы информации [45].

Теорема 1. Если пропускная способность канала С такого, что С > Н /Т, где Н — энтропия источника, Т - интервал времени передачи, то можно закодировать сообщение этого источника так, чтобы вероятность правильного приема была равна 1- е, где с - сколь угодно малое число.

• Теорема 2. Пусть С пропускная способность канала и Н /Т > С, тогда можно так закодировать сообщение источника, чтобы скорость передачи информации была сколько угодно близка к Н IT. Это обеспечивает передачу сообщений по каналу со сколь угодно малой ненадежностью.

За последние годы интерес к теории информации и, в частности, к построению статистических методов кодирования для источника резко увеличился.

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

Но, несмотря на достижения в области методов сжатия информации и кодирования источника, существует ряд нерешенных проблем. Например, теоретически доказано, что неравномерные коды лучше, чем равномерные, при кодировании и символов источника. Но все-таки до сих пор все больше используются равномерные коды [49, 59]. Дело в том, что неравномерные коды обладают следующими существенными недостатками [46]:

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

А Л

ЦЕЛЬ НАСТОЯЩЕЙ РАБОТЫ: разработка алгоритма кодирования с минимальным распространением ошибок по символам сообщения в неравномерных кодах.

НАУЧНАЯ НОВИЗНА состоит в новом принципе кодирования сообщения при помощи кодов с двумя специфическими частями кодовых символов префиксом и информационной частью.

НА ЗАЩИТУ ВЫНОСЯТСЯ следующие научные результаты, полученные лично автором:

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

2. Предложен новый класс кодов с двумя группами для кодирования источников.

3. Разработано устройство декодирующее предлагаемый код.

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

5. Установлена корреляция между буквами вне зависимости от объема текста.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Работа носит теоретический и приклад-« ной характер. Полученные в ней результаты являются развитием теории кодирования источника и разработанные устройства могут быть использованы на практике.

АПРОБАЦИЯ РАБОТЫ. Результаты работы докладывались на международных научно-технических конференциях студентов и аспирантов и также в журнале «Радиотехнические тетради» [48,49,50].

ПУБЛИКАЦИИ. По теме диссертации автором опубликованы 5 работ [48,49,50,51,52].

СТРУКТУРА ДИССЕРТАЦИИ. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и приложение.

Заключение диссертации по теме «Радиотехника, в том числе системы и устройства телевидения», Нго Биссе Жаки Терез

Основные результаты полученные в диссертации:

1. Рассмотрена обобщенная классификация кодов по разным критериям. Уделено внимание статистическому кодированию.

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

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

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

5. По теме диссертации автором опубликованы 5 работ [48,49,50,51,52].

Заключение

Список литературы диссертационного исследования кандидат технических наук Нго Биссе Жаки Терез, 2004 год

1. Баева Н. Н. И др. Многоканальные системы передачи. М.: Радио и связь, 1997.

2. Банкет B.JI. Сверточные коды в системах передачи информации. Одесса: Изд. Электротех. Ин-т связи, 1986.

3. Баскаков А. И и др. Зондирующие радиолокационные сигналы. М.: Изд. МЭИ, 1990.

4. Баскаков С. И. Радиотехнические цепи и сигналы. М.: Высшая школа, 2000.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

6. Борисов В. А. и др. под ред. Калмыкова В.В. Радиотехнические системы передачи информации. М.: Радио и связь, 1990.

7. Бриллюэн JI. Наука и теория информации. М.: Изд. Физ-мат. 1960.

8. Вентцель Е.С. Теория вероятностей. М.: Изд. Наука, 1969.

9. Гармаш В.А. Исследование статистики сигналов и сообщений и методы статистического кодирования. Диссертация. М.: МЭИС, 1959.

10. Гитлиц М. В., Лев А. Ю. Теоретические основы многоканальной связи. М.: радио и связь 1985.

11. Зюко А.Г., Кловский Д. Д., Назаров М. В., Финк Л.М. Теория передачи сигналов. М. Радио и связь, 1986.

12. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987.

13. Колмогоров А. Н. Алгоритм, информация, сложность. М.: Знание, 1991.

14. Кричевский Р.Е. Сложность сжатия информации. Диссертации. Новосибирск, 1985.

15. Кричевский Р.Е. Сжатие и поиск информации. М.: Изд. Радио и связь, 1989.

16. Лазарева Е.Е. Циклические и сверточные коды. М.: МЭИ, 1986.

17. Левенштейн В.И. Самонастраивающийся автоматы для декодирования сообщений. // Доклады Академии Наук СССР. Т. 141, 1961. №6, стр. 13201323.

18. Левенштейн В. И. Элементы теории кодирования. // Дискретная математика и математические вопросы кибернетики. Изд. Физ. Мат. Т.1. 1974.

19. Лёч М. Исследование некоторых методов специального кодирования источника. Диссертация. Москва, 1977.

20. Липкин И. А. Статистическая радиотехника. Теория информации и кодирования. М.: Вузовская книга, 2002.

21. Мейерс С. Наиболее эффективное использование С++. М.: Дмк Пресс, 2000.

22. Макаров А.А., Гернецкий Г. А. Корректирующие коды в системах передачи информации. Новосибирск: Гос. Ун-т Телекоммуникации и информатики, 2000.

23. Мак-Вильямс и др. Теория кодов и исправляющих ошибки. М.: Изд. Связь, 1979.

24. Марков А. А. Введение в теорию кодирования. М. Изд. Наука, 1982.

25. Нарышкин А. К. Информативность радиолокационных объектов, сигналов и систем. М.: МЭИ, 1994.

26. Нарышкин А.К. Основы теории радиотехнических систем извлечения информации. М.: МЭИ, 1996.

27. Нарышкин А.К. Основы статистического кодирования. М.: Изд. МЭИ, 2002.

28. Нарышкин А. К. Комбинационные Цифровые устройства. М.: Изд. МЭИ, 2002.

29. Никитин Г. И., Подцубный С. С. Помехоустойчивые циклические коды СПБ.: Гос. Ун-т аэрокосм. Приборостроение, 1998.

30. Норенков И. П. и др. Телекоммуникационные технологии и сети. М.: МГТУ, 2000.

31. Петцольд Ч. Код—тайный язык информатики. М.: Русская редакция, 2001.

32. Прокис Д. Цифровая связь. М.: Радио и связь, 2000.

33. Сергириенко А. Б. Цифровая обработка сигналов. СПБ.: Питер, 2003.

34. Симонович С.В. Информатика (учебник для вузов). СПБ.: Питер, 2001.

35. Стиффлер Дж. Дж. Теория синхронной связи. М.: Изд. Связь, 1975.

36. Суприн Б. А. Первичные коды. М.: Связь, 1970.

37. Трофимов В. К. Кодирование источников с неизвестной и неточно известной статистикой сообщений. Диссертация. Новосибирск, 1988.

38. Универсальная десятичная классификация (сокращенные таблицы) М.: машиностроение, 1999.

39. Фано Р. Передача информации. Статистическая теория связи. М.: Изд. Наука, 1965.

40. Фитингоф Б.М. Сжатие дискретной информации. // Проблемы передачи информации. Т. 3, 1967, № 3, стр. 28-36,.

41. Харкевич А.А. Очерки общей теории связи. М.: Гостехизд.1955.

42. Хаффмен Д.А. Метод построения кодов с минимальной избыточностью. // Кибернетический сборник. 1963, вып. 3.

43. Хенкок, Лес и др. Введение в программирование на языке С. М.: Радио и связь, 1986.

44. Цымбал В. П. Теория информации кодирование. К.: Изд. Вища школа, 1982.

45. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ., 1963.

46. Шувалов В.П. Передача дискретных сообщений. М.: Радио и связь, 1990.

47. Якубовский С. В. и др. Цифровые и аналоговые интегральные микросхемы: справочник. М.: Радио и Связь, 1990.

48. Нго Биссе Ж. Т., А.К. Нарышкин Обобщение классификации информационных кодов. // 6-ая международная научно-техническая конференция студентов и аспирантов. «Радиоэлектроника, электротехника и энергетика»: Тез. Докл.- М.:Изд.МЭИ,2000-Т. 1-С. 100-101.

49. Нго Биссе Ж. Т., А.К. Нарышкин Исследование статистических кодов. // 8-ая международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. Докл. — М.: Изд. МЭИ, 2002. -Т.1- С 107.

50. Нго Биссе Ж. Т. Статистика попарной корреляции букв французского и русского текстов и количество информации, содержащееся в них // Радиотехнические тетради -2003. № 26. С. 78-80.

51. Нго Биссе Ж. Т. Исследование средней длины неравномерного кодирования и борьба с ошибкой синхронизации // Радиотехнические тетради— 2003. № 26. С. 76-78.

52. Andrian Е., Perkins Е., Perkins S. Binary Huffman equivalent codes with a short synchronizing codeword. // IEEE. Inform. Theory. Vol. 44, № 1, pp-346. January 1998.

53. Battail G. Codage de source adaptif par Palgorithme de Guazzo. // Annales des telecommunications. Vol. 45, № 11-12, p. 679.1990.

54. Beulah Rudner, Construction of minimum-redundancy codes with an optimum synchronizing property. // ,IEEE. Trans.Inform. Theory, vol.17, № 4, pp. 478487, July 1971.

55. Cohen G., Charpin. Eurocode 90. Lecture notes in computer. Udine-Italy, 1990.

56. Davisson L. Universal noiseless coding. // IEEE Trans. Inf. Theory. Vol 19, № 6, pp. 783-795,1973.

57. Ferguson Thomas J., Rabinowitz Joshua H., Self synchroning Huffman codes. // IEEE. Trans. Inform.Theory. Vol. 30, № 4, pp. 687-692 July 1984.

58. Fong A.C.M., Higgie G.R., Fong B. Multimedia applications of self-synchronizing T-codes. // International conference on Inform. Technology coding and computing, pp. 519 523, Las vegas, Nevada 2001.

59. Gilbert E.N., Moore E. F. Variable length binary encodings. // Bell syst. Tech. vol.38, 1959.

60. Hagenauer J., Bauer R. The Turbo Principle in Joint Source Channel Decoding of Variable Length Codes. // Proc. IEEE Information Theory Workshop, Cairns, Australia, pp. 33-35, Sept. 2001.

61. Johnsen O. On the redundancy of binary Huffman codes. // IEEE. Trans. Inform. Theory. Vol. 26, № 2, pp. 220-222, March 1980.

62. Langdon G. G. Comment on "A Universal Data Compression System". // IEEE. Trans. Inform. Theory. Vol. 32, № 6, p. 857, Nov. 1986.

63. Maxted J. C., Robinson J. P. Error recovery for variable length codes. // IEEE. Trans. Inform. Theory. Vol31, № 6, pp. 794-801, Nov. 1985.

64. Minimax E. P. Optimal universal codework set. // IEEE. Trans. Inf. Theory. Vol. 29 № 4, pp. 491-502, 1983.

65. Moffat Alistair. Implementing the PPM data compression scheme. // IEEE. Trans. Inform. Theory. Vol. 38, №11, pp. 1917-1921. Nov. 1990.

66. Montgomery B. L., Abrahams J. Synchronization of binary sources codes. // IEEE. Trans. Inform. Theory. Vol. 32, № 6, pp. 849-857, Nov. 1986.

67. Neumann P. G. Efficient error-limiting variable-length codes. // IRE. trans, of inf. Theory, pp. 292-304, July 1961.

68. Pascal B. Pensees Classique francais. Paris, 1995.

69. Ryabko B. Y. Fast and effective coding of information sources. // IEEE. Trans. Inf. Theory. Vol. 40, № 1, p. 96-99. 1994.

70. Ziv J., Lempel A. An universal algorithm for sequental Data Compression. // IEEE Transactions of Information Theory. Vol, 23, № 3, p. 337. May 1977.

71. Ziv J., Lempel A. Compression of individual sequences via variable- rate encoding. // IEEE. Trans. Inform. Theory. Vol. 24, № 5, p. 530-536. Sept. 1978.