Изменения
Нет описания правки
# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
# При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 2 битов
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
# Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
# Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
# Разработайте код Грея для k-ичных векторов
# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
# Код "антигрея" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
# Троичный код "антигрея" - постройте троичный код, в котором соседние слова отличаются во всех позициях
# При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
# Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
# Докажите корректность следующего алгоритма построения цепного кода. Начинаем со строки из $n$ нулей. Каждый раз пытаемся жадно приписать 1, если слово из последних $n$ символов уже встречалось раньше, то приписываем 0. Заканчиваем, когда все $2^n$ слов получены.
