Алгоритмы кодирования и сжатия

Здесь представлена реализация некоторых простых алгоритмов кодирования и сжатия в рамках курса Компьютерные сети (8 семестр).

Алгоритмы

1. CRC (Cyclic Redundancy Code)
2. Код Хэмминга
3. Код Шеннона-Фано
4. Код Хаффмана

1. CRC

Клиент/сервер. Запуск сервера, потом - клиента. На клиенте производится ввод текстового сообщения. После этого с вероятностью, близкой к 0.5, вносится случайная ошибка. Далее сообщение отправляется на сервер.

На сервере происходит получение сообщения от клиента, его раскодирование CRC. В случае ошибки, сервер запрашивает повторную отправку сообщения от клиента. Так происходит, пока сообщение не будет доставлено успешно.

Пример:

Client

Server

Введите сообщение для отправки на сервер: >? Peter Сообщение в двоичном виде: 0101000001100101011101000110010101110010 Закодированное сообщение, готовое к отправке: 0101000001100101011101000110010101110010000 Ответ от сервера: Сообщение успешно доставлено! Введите сообщение для отправки на сервер: >? Parker Сообщение в двоичном виде: 010100000110000101110010011010110110010101110010 Закодированное сообщение, готовое к отправке: 010100000110000101110010011010110110010101110010110 Внесена ошибка в 24 бите: 010100000110000101110010111010110110010101110010110 Ответ от сервера: Произошла ошибка при отправке! Попытка повторной отправки... Сообщение в двоичном виде: 010100000110000101110010011010110110010101110010 Закодированное сообщение, готовое к отправке: 010100000110000101110010011010110110010101110010110 Ответ от сервера: Сообщение успешно доставлено! Введите сообщение для отправки на сервер:

Подключено: ('127.0.0.1', 59695) Полученные данные: 0101000001100101011101000110010101110010000 Получено сообщение: Peter Полученные данные: 010100000110000101110010111010110110010101110010110 При отправке произошла ошибка. Отправляю запрос на переотправку... Полученные данные: 010100000110000101110010011010110110010101110010110 Получено сообщение: Parker

2. Код Хэмминга

Клиент/сервер. Запуск сервера, потом - клиента. На клиенте производится ввод текстового сообщения. После этого с вероятностью, близкой к 0.5, вносится случайная ошибка. Далее сообщение отправляется на сервер.

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

Пример:

Client

Server

Введите сообщение для отправки на сервер: >? Peter Сообщение в двоичном виде: 0101000001100101011101000110010101110010 Закодированное сообщение, готовое к отправке: 0100101000000111001010111010001110010101110010 Ответ от сервера: Сообщение успешно доставлено! Введите сообщение для отправки на сервер: >? Parker Сообщение в двоичном виде: 010100000110000101110010011010110110010101110010 Закодированное сообщение, готовое к отправке: 110110100000011000001011100100101010110110010101110010 Внесена ошибка в 7 бите: 110110110000011000001011100100101010110110010101110010 Ответ от сервера: Сообщение успешно доставлено!

Полученные данные: 0100101000000111001010111010001110010101110010 Получено сообщение: Peter Полученные данные: 110110110000011000001011100100101010110110010101110010 Исправлена ошибка в 7 бите: 010100000110000101110010011010110110010101110010 Получено сообщение: Parker

3. Код Шеннона-Фано

Программа берёт текстовый файл, кодирует его алгоритмом Шеннона-Фано и оценивает эффективность сжатия.

4. Код Хаффмана

Программа берёт текстовый файл, кодирует его алгоритмом Хаффмана и оценивает эффективность степень сжатия. Сравнить эффективность сжатия с кодом Шеннона-Фано.

Вывод:

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

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