Оптимизация частоты нулей и единиц
Я тут провёл небольшое исследование на тему оптимального соотношения нулей и единиц в стандартном кассетном формате.
Известно, что стандартный формат записывает бит "0" последовательностью кодированных бит "10", а бит "1" - последовательностью "1100", которая в 2 раза длиннее. Таким образом, файл, состоящий из одних нулей, будет загружен в 2 раза быстрее файла, состоящего из одних единиц (или #FF).
Разумеется, файл с нулями или FF-ами не несёт никакой информации. Обычно, если файл скомпрессирован или состоит из случайных данных - то количество нулевых бит в нём примерно равно количеству единиц. Таким образом, получается, что средняя скорость записи случайных данных равна среднему арифметическому между скоростями записи одних нулей и одних единиц.
Если изменить соотношение нулей и единиц в файле; скажем, сделать так, чтобы только 20% всех бит были равны единице - то средняя скорость записи возрастёт. Хотя останется неясным, сколько же информации можно передать таким способом. Я рассмотрел вопрос с точки зрения энтропии по Шеннону.
Для двоичного сигнала энтропия (т.е. информационная ёмкость) каждого бита H0 = -p*log2(p)-(1-p)*log2(1-p), где p - вероятность того, что бит равен 1. Легко проверить, что при p=0.5 энтропия равна 1, а также то, что при этом p достигается максимальная информационная ёмкость сигнала.
При рассмотрении энтропии не полезного, а кодированного сигнала, записываемого на кассету в стандартном спектрумовском формате, нужно учесть, что нули и единицы имеют разную длительность. Длительность каждого кодированного бита равна в среднем 2+2*p, где за единицу измерения взят минимальный интервал между фронтами. Таким образом, энтропия кодированного сигнала на этом интервале равна H1=(-p*log2(p)-(1-p)*log2(1-p))/(2+2*p)
Для нахождения процентного соотношения нулей и единиц, при котором H1 достигает максимума, нужно найти производную H1 и приравнять её к нулю. Производная H1' = (-log2(p)+2*log2(1-p))/(2*(1+p)^2). Решая уравнение H1'=0, находим два корня, один из которых соответствует p>1, и потому не подходит, а второй корень равен p*=(3-sqrt(5))/2, что примерно равно 38.2%. Таким образом, когда примерно 38% всех бит в файле равны 1, а остальные равны 0, достигается максимальная энтропия на единицу времени кодированного сигнала и тем самым максимальная плотность записи в спектрумовском формате. Подставив значение p* в формулу для H1, находим, что H1*~=0.347, что несколько выше значения H1 при p=0.5, которое составляет 0.333.
Таким образом, оптимизация соотношение нулей и единиц в файлах стандартного формата позволяет повысить плотность записи информации, хотя лишь незначительно - на 4.1%.
Ввиду незначительности выигрыша, я не вижу смысла в разработке программной реализации. Но, чисто теоретически, она могла бы выглядеть так:
1) Компрессия файла наилучшим возможным образом
2) Обработка преобразованием, меняющим частоту нулевых и единичных бит. Длина файла при этом в среднем вырастет на 4.2%, однако загрузится такой файл на 4.1% быстрее, чем если сохранить исходную информацию без преобразования.
3) Сохранение обработанного файла
При загрузке обработка идет в обратной последовательности:
4) Загрузка
5) Преобразование, обратное проведенному на шаге 2)
6) Декомпрессия.
Полученный результат имеет ту ценность, что спектр кодированного сигнала наиболее близок к белому шуму при соотношении нулей и единиц, равному p*.
Привожу получившиеся картинки и исходный код программы для расчета. Программа работает под GNU Octave, также можно ее запускать на Matlab. С помощью программы можно поэкспериментировать и убедиться, что найденное соотношение кол-ва нулей и единиц действительно является оптимальным. Также для тех, кто еще не видел спектрального анализа сигналов, записанных в стандартном спектрумовском формате, в аттаче находится спектрограмма.
Ответить с цитированием
Сообщение от Barmaley_m
Размещение рекламы на форуме способствует его дальнейшему развитию 
