2020-06-30
849К лабораторной работе 1:
1. Кодирование целых сообщений. Вводится m – число кодируемых сообщений. Программа формирует и выводит на экран m двоичных кодовых слов равной длины с числом разрядов, определяемым по формуле 1.
2. Посимвольное кодирование сообщений. Вводится m сообщений различной длины, составленных из символов некоторого алфавита. Программа кодирует все символы алфавита равномерным двоичным кодом с числом разрядов, определяемым по формуле 2, и выводит на экран m кодовых комбинаций, полученных путем объединения двоичных кодов, соответствующих символам введенных сообщений.
3. Определение даты по ее номеру в диапазоне. Вводится дата (число, месяц, год) начала и конечная дата некоторого диапазона, а также некоторое число в пределах размерности этого диапазона дат. Программа определяет и выводит точное значение даты, соответствующее указанному числу. При выходе числа за пределы размерности диапазона выдается сообщение об ошибке.
4. Определение номера даты в диапазоне. Вводится дата (число, месяц, год) начала и конечная дата некоторого диапазона, а также некоторая другая дата, принадлежащая данному диапазону дат. Программа определяет и выводит значение номера последней введенной даты в указанном диапазоне. При выходе этой даты за пределы диапазона выдается сообщение об ошибке.
5. Подавление повторяющихся символов. Вводится последовательность строк, составленных из символов некоторого алфавита. В каждой строке, содержащей последовательность повторяющихся подряд символов, последняя заменяется эквивалентной последовательностью вида *(k)a, где k – число повторений некоторого символа «a».
6. Кодирование часто используемых данных. Вводится m различных терминов некоторой предметной области, а также несколько строк текста, содержащего данные термины. Программа кодирует каждый из введенных терминов равномерным двоичным кодом и заменяет его в тексте на соответствующий код.
7. Сжатие на основе сравнения. Вводится m различных сообщений произвольной длины, последовательности начальных символов в которых могут совпадать. Если такое совпадение имеется в двух сообщениях, следующих друг за другом, то начальные символы второго сообщения заменяются программой на эквивалентное представление вида *(k), где k – количество совпадающих символов.
8. Кодирование префиксным кодом. Вводится m – число кодируемых сообщений. Программа генерирует и выводит m двоичных кодовых слов произвольной длины, образующих префиксный код.
9. Декодирование префиксным кодом. Имеется префиксный код, состоящий из m двоичных кодовых слов различной длины, которым закодировано m символов некоторого алфавита А. Вводится последовательность двоичных символов произвольной длины и программа осуществляет попытку ее декодирования в указанные символы с выдачей результата декодирования или сообщения об ошибке.
10. Проверка префиксности кода. Вводится код из m двоичных кодовых слов произвольной длины, для которого программа проверяет условие префиксности и выдает на экран результат проверки.
11. Проверка примитивности префиксного кода. Вводится префиксный код из m двоичных кодовых слов произвольной длины, для которого программа проверяет условие примитивности и выдает результат проверки. Указание: задание основывается на результатах выполнения предыдущего задания.
12. Определение средней длины кодового слова. Вводится m – число кодируемых сообщений, m двоичных кодов различной длины, используемых для кодирования, и m вероятностей появления данных сообщений. Программа нормирует все введенные вероятности, приводя их сумму к единичному значению, после чего вычисляет и выводит среднюю длину кодового слова.
13. Кодирование двухсимвольных последовательностей. Вводятся два символа некоторого алфавита, вероятности их появления и составленная из них произвольная последовательность, длина которой кратна двум. Программа выполняет следующие функции:
а) проверка и нормирование вероятностей появления символов;
б) проверка длины введенной последовательности на четность и отбрасывание последнего символа в случае нарушения четности;
в) генерация всех возможных различных двухсимвольных комбинаций и их экономное двоичное кодирование;
г) разбиение введенной последовательности на двухсимвольные комбинации, замена их на сгенерированные двоичные коды и формирование результирующей последовательности путем сцепления полученных двоичных кодов;
д) вывод результирующей последовательности на экран.
14. Кодирование трехсимвольных последовательностей. Вводятся три символа некоторого алфавита, вероятности их появления и составленная из них произвольная последовательность, длина которой кратна трем. Программа выполняет следующие функции:
а) проверка и нормирование вероятностей появления символов;
б) проверка длины введенной последовательности на кратность трем и отбрасывание одного или двух последних символов в случае нарушения кратности;
в) генерация всех возможных различных трехсимвольных комбинаций и их экономное двоичное кодирование;
г) разбиение введенной последовательности на трехсимвольные комбинации, замена их на сгенерированные двоичные коды и формирование результирующей последовательности путем сцепления полученных двоичных кодов;
д) вывод результирующей последовательности на экран.
15. Кодирование процедурой Шеннона - Фано. Вводится m – число кодируемых сообщений и m вероятностей появления данных сообщений. Программа нормирует все введенные вероятности, приводя их сумму к единичному значению, после чего осуществляет кодирование сообщений в соответствии с алгоритмом Шеннона – Фано (см.[5]) и выводит на экран m сгенерированных двоичных кодов, а также их рассчитанную среднюю длину. Указание: задание повышенной сложности.
16. Кодирование процедурой Хафмана. Вводится m – число кодируемых сообщений и m вероятностей появления данных сообщений. Программа нормирует все введенные вероятности, приводя их сумму к единичному значению, после чего осуществляет кодирование сообщений в соответствии с алгоритмом Хафмана (см.[5]) и выводит на экран m сгенерированных двоичных кодов, а также их рассчитанную среднюю длину. Указание: задание повышенной сложности для особо интересующихся программированием.
К лабораторной работе 2:
1. Кодирование путем повторения символов. Вводится m – нечетное число, задающее кратность повторения, а также последовательность двоичных символов произвольной длины. Программа проверяет нечетность числа m и выдает сообщение об ошибке, если m – четное. В противном случае формируется и выводится на экран результирующая последовательность, в которой каждый символ входной последовательности повторяется m раз подряд.
2. Декодирование путем повторения символов. Вводится m – нечетное число, задающее кратность повторения, а также последовательность двоичных символов, длина которой кратна m. Если кратность нарушена, то последние символы последовательности игнорируются. В каждой комбинации из m символов путем сравнения числа нулей с числом единиц определяется результат декодирования (ноль или единица), который помещается в результирующую последовательность, выводимую на экран по окончании декодирования всей входной последовательности символов.
3. Кодирование методом контроля четности. Вводится k – число символов в блоке и последовательность двоичных символов, длина которой кратна (k-1). Если кратность нарушается, то последние символы последовательности игнорируются. Для каждой комбинации из (k-1) символов по методу контроля четности определяется значение k-го, контрольного, символа и вся комбинация из k символов добавляется в результирующую последовательность, выводимую на экран по окончании кодирования всей входной последовательности символов.
4. Декодирование методом контроля четности. Вводится k – число символов в блоке и последовательность двоичных символов, длина которой кратна k. Если кратность нарушается, то последние символы последовательности игнорируются. В каждой комбинации из k символов осуществляется проверка четности: если четность не нарушена, то первые (k-1) символов данной комбинации добавляются в результирующую последовательность, если же четность нарушается, то счетчик количества ошибок увеличивается на единицу. По окончании декодирования всей входной последовательности символов результирующая последовательность, а также значение счетчика ошибок выводятся на экран.
5. Кодирование методом контрольных сумм. Вводится последовательность двоичных символов, длина которой кратна четырем (если кратность нарушается, то последние символы игнорируются). Для каждой четверки символов по методу контрольных сумм определяются значения трех контрольных символов, после чего все семь символов добавляются к результирующей последовательности, выводимой на экран по окончании кодирования всей входной последовательности символов.
6. Декодирование методом контрольных сумм. Вводится последовательность двоичных символов, длина которой кратна семи (если кратность нарушается, то последние символы игнорируются). Для каждой семерки символов определяется четность контрольных сумм и исправляется выявленная однократная ошибка, после чего первые четыре символа добавляются к результирующей последовательности, выводимой на экран по окончании декодирования всей входной последовательности символов.
7. Вычисление минимального кодового расстояния. Вводится k – длина кодового слова и несколько двоичных кодовых комбинаций длины k (если длина комбинаций отлична от k, то выдается сообщение об ошибке). Программа вычисляет и выводит минимальное кодовое расстояние (расстояние Хэмминга) между данными комбинациями.
