Файл: Методы кодирования данных (ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КОДИРОВАНИЯ ДАННЫХ).pdf

(1)

(2)

(3)

где: t_о – число обнаруживаемых ошибок,

t_и – число исправляемых ошибок.

Циклические коды – это подкласс линейных кодов, коды которого удовлетворяют следующим циклическим свойствам: если - кодовое слово кода, тогда полученное циклическим сдвигом элементов кода C, также являются кодовым словом. Все циклические сдвиги слова С образуют кодовые слова.

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

Алгоритм контрольного суммирования

Алгоритм контрольного суммирования CRC -Cyclic redundancy check- предназначается для контроля целостности данных. Он широко используется в проводных и беспроводных сетях, в устройствах хранения данных, для проверки информации на подлинность и защиты от несанкционированного изменения. В универсальной последовательной шине USB каждый пакет имеет поля CRC, позволяющие обнаруживать все однократные и двукратные битовые ошибки.

CRC предназначен не для исправления ошибок, а для их обнаружения.

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

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

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

CRC-8: x⁸ + x⁷ + x⁶ + x⁴ + x² + 1 – используется формой Dallas Semiconductor в устройствах низкоскоростной связи.

CRC-16-IBM (CRC-16 или CRC-16-ANSI): x¹⁶ + x¹⁵ + x² + 1 – используется в ANSI X3.28, в интерфейсах USB, ModBus и других линиях связи.

CRC-32: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1 – используется при кодировании видео и аудио сигналов с использованием стандарта MPEG-2, при кодировании растровых изображений в формате PNG и во многих других случаях.

Отметим, что приведенные порождающие многочлены не являются единственными для CRC-8, CRC-16, CRC-32. Разные полиномы для одних и тех же CRC используются для разных технологий и в разных стандартах.

Коды Боуза-Чоудхури-Хоквингема (БЧХ).

Перспективными с точки зрения аппаратурной реализации представляются коды БЧХ. Коды БЧХ длины примерно до n=1023 оптимальны или близки к оптимальным кодам. БЧХ-коды представляют большой класс циклических кодов как с двоичным, так и с недвоичным алфавитами.

Этот класс двоичных кодов позволяет исправлять ошибки. Причем метод построения этих кодов задан явно.

Коды БЧХ отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а также предоставляет разработчику систем связи широкий выбор длин блока и скоростей кода. БЧХ-коды могут исправлять произвольное количество ошибок. Однако с ростом кратности ошибки значительно возрастает длина кода, что ведет к уменьшению скорости передачи и усложнению приемно-передающей аппаратуры.

БЧХ-код можно задать порождающим полиномом. Для его нахождения в необходимо заранее определить длину кода n и требуемое минимальное расстояние .

Порождающие полиномы для БЧХ кодов можно конструировать из множителей полинома .

Общий список порождающих полиномов для БЧХ кодов дан Питерсоном и Уэлдоном, которые дали таблицы множителей полиномов для .

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

Коды Рида-Соломона

Частным случаем БЧХ-кода являются коды Рида-Соломона.

Коды Рида-Соломона – это недвоичные циклические коды, предназначенные для исправления пачек ошибок.

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

Благодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин. Для компакт-диска избыточность кода в среднем составляет примерно 25 %. Восстанавливаемое количество данных равно половине избыточных. Так, если емкость диска 700 Мб, то количество избыточных данных составит 175 Мб. Таким образом, теоретически можно восстановить до 87,5 Мб из 700 Мб. При этом нам не обязательно знать, какой именно символ передан с ошибкой.

ЗАКЛЮЧЕНИЕ

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

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

Рассмотрены основные понятия и принципы кодирования информации;

Изучен метод кодирования Хаффмана.

Изучены алгоритмы кодирования информации для реализации программного продукта «Код Хаффмана», с использованием современной технологии программирования;

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

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

До появления работ Шеннона, Фано а позже и Хаффмана, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этих работ начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, то есть более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего).

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Алгоритмы LZW, LZ77 и LZ78 [Электронный ресурс]. — Режим доступа: http://ru.wikipedia.org/?oldid= 68967235.- (Дата обращения: 10.02.2017).
2. Алгоритмы сжатия RLE и LZ77 [Электронный ресурс]. – Режим доступа: http://habrahabr.ru/post/141827/. - (Дата обращения: 09.02.2017).
3. Бернард Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2013. – 1104 с., ил. – Парал. тит. англ.
4. Вильям Столлингс. Компьютерные системы передачи данных, 6-е издание. : Пер. с англ. – М.: Издательский дом «Вильямс», 2016. – 928 с., ил. – Парал. тит. англ.
5. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова – СПб.: Питер, 2011 – 576с.
6. Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев – М.: Вильямс, 2014. – 288с.
7. Дж. Ирвин, Д. Харль. Передача данных в сетях: инженерный подход. Пер. с англ. – СПб.: БХВ – Петербург, 2013. – 448 с., ил.
8. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 320с.
9. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен – Киев: ДиаСофт, 2015. – 544с.
10. Карпенко А.С., Крысова И.В. Использование графического формата MNG для сжатия изображений в веб-программирвании. – Информационные технологии в науке и производстве : материалы молодежной науч.-техн. конф.– Омск : Изд-во ОмГТУ, 2015. С. 91-94.
11. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер – М.: «Диалектика», 2012 – 272с.
12. Меняев М.Ф. Информатика и основы программирования / М.Ф. Меняев – М.: Омега-Л, 2017 – 458с.
13. Методы сжатия цифровой информации [Электронный ресурс]. - Режим доступа: http://eae-1.clan.su/informat/dist/lekcija.pdf.- (Дата обращения: 10.02.2017).
14. Новиков Ю.В., Карпенко Д.Г. Аппаратура локальных сетей: функции, выбор, разработка. / Под общей редакцией Ю.В. Новикова. – М.: Издательство ЭКОМ, 2016.–288 с.,ил.
15. Савельев Б.А. Повышение достоверности передачи и хранения информации в компьютерных сетях: Учебное пособие. – Пенза: Изд-во Пенз. гос. ун-та, 2016. – 80 с., ил.
16. Тропченко А.Ю., Тропченко А.А. Методы сжатия изображений, аудиосигналов и видео. – СПб: СПбГУ ИТМО, 2009. – 108 с.
17. Тропченко А.Ю., Тропченко А.А. Методы сжатия изображений, аудиосигналов и видео. – СПб: СПбГУ ИТМО, 2009. – 108 с.