Вопросы по теории информации, энтропии и информационному наполнению различных источников
Все ли строки азбуки Морзе однозначно расшифрованы? Без пробелов, ......-...-..---.-----.-..-..-.. может быть, Hello Worldно, возможно, первая буква 5- на самом деле это выглядит очень маловероятным, произвольная последовательность точек и тире должна иметь уникальный перевод. Можно использовать...
Эта идея пришла мне в голову, когда я учился программировать и впервые столкнулся с PRNG. Я до сих пор не знаю, насколько это реалистично, но сейчас происходит обмен стека. Вот схема 14-летнего ребенка для удивительного алгоритма сжатия: Возьмите PRNG и начните его с seed, sчтобы получить длинную...
Согласно Википедии : Энтропия Шеннона измеряет информацию, содержащуюся в сообщении, в отличие от той части сообщения, которая определена (или предсказуема). Примеры последних включают избыточность в структуре языка или статистических свойствах, связанных с частотой встречаемости пар букв или слов,...
Скажем, мне нужно смоделировать следующее дискретное распределение: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} Наиболее очевидный способ - нарисовать случайных битов и...
У меня есть файл, содержащий упорядоченные двоичные числа от до 2 n - 1 :0002n−12n−12^n - 1 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z не сжимал этот файл очень эффективно (при n = 20 22 МБ были сжаты до 300 кБ). Существуют ли алгоритмы, которые могут распознать очень...
Я читаю книгу: « Код: скрытый язык компьютерного оборудования и программного обеспечения » и в главе 2 автор говорит: Говорят, что азбука Морзе является двоичным (буквально означающим два на два) кодом, потому что компоненты кода состоят только из двух вещей - точки и тире. Википедия с другой...
Недавно я наткнулся на следующую интересную статью, в которой утверждается, что эффективное сжатие случайных наборов данных всегда более чем на 50%, независимо от типа и формата данных. В основном он использует простые числа для уникального построения представления 4-байтовых блоков данных, которые...
Сравнивая упорядоченную пару (x, y) с неупорядоченной парой {x, y} (set), затем теоретически определяем, что разница составляет всего один бит, так как x идет первым или y требуется ровно один бит для представления. Итак, если нам дан набор {x, y}, где x, y - два разных 32-разрядных целых числа,...
Чтобы зашифровать сообщение с помощью ключа одноразовой клавиатуры k , выполните E n c ( m 1 , k ) = m 1 ⊕ k .м1m1m_1КkkЕn c ( м1, к ) = м1⊕ кEnc(m1,k)=m1⊕kEnc(m_1,k) = m_1 \oplus k Если вы используете одно и то же для шифрования другого сообщения m 2, вы получите E n c ( m 2 , k ) = m 2 ⊕ k , а...
У вас есть массив из отдельных элементов. У вас есть доступ к компаратору (функция черного ящика, принимающая два элемента и и возвращающая true, если ) и действительно случайный источник битов (функция черного ящика, не принимающая аргументов и возвращающая независимо равномерно случайный бит)....
Я читал об алгоритмах сжатия данных и теоретическом пределе для сжатия данных. Недавно я столкнулся с методом сжатия под названием «Комбинаторное энтропийное кодирование», основная идея этого метода заключается в кодировании файла в виде символов, представленных в файле, их частоты и индекса...
Указание любой произвольной сетки 9x9 требует указания позиции и значения каждого квадрата. Наивное кодирование для этого может дать 81 (x, y, значение) триплетов, требуя 4 бита для каждого x, y и значения (1-9 = 9 значений = 4 бита) в общей сложности 81x4x3 = 972 бита. При нумерации каждого...
Согласно Википедии : Неформально, с точки зрения алгоритмической теории информации, информационное содержание строки эквивалентно длине кратчайшего возможного автономного представления этой строки. Каково аналогичное неофициальное строгое определение «полезной информации»? Почему «полезная...
Учитывая строку значений энтропии Шеннона в логарифм приходит к 0,922 . Из того, что я понимаю, в базе 2 энтропия Шеннона, округленная в большую сторону, является минимальным числом битов в двоичном коде, чтобы представить одно из значений.AAAAAAAABCAAAAAAAABCAAAAAAAABC2220.9220.9220.922222 Взято...
В настоящее время я пишу код для генерации двоичных данных. Мне конкретно нужно генерировать 64-битные числа с заданным количеством установленных битов; Точнее, процедура должна занять около 0<n<640<n<640 < n < 64 и вернуть псевдослучайное 64-битное число с точно nnn битами,...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Пытаясь понять взаимосвязи между кодированием Хаффмана, арифметическим кодированием и дистанционным кодированием, я начал думать о недостатках кодирования Хаффмана, связанных с проблемой дробной битовой упаковки . То есть, предположим, что у вас есть 240 возможных значений для символа, и вам...
В теории кодирования «насколько хорош код» означает, сколько ошибок канала можно исправить, или, лучше сказать, максимальный уровень шума, с которым может справиться код. Чтобы получить лучшие коды, коды разработаны с использованием большого алфавита (а не двоичного). И потом, код хорош, если он...
Требование кодирования без префикса приводит к большим деревьям из-за того, что дерево должно быть завершено. Существует ли порог, в котором некодированное хранение данных фиксированной длины будет более эффективным, чем кодирование...
Задача состоит в том, чтобы доказать или опровергнуть существование , st, ; ; d (c_i, c_j) \ geq2,1 \ leq i <j \ leq32 . ( d обозначает расстояние Хэмминга)ССC|с | = 6 , ∀ c ∈ C|с|знак равно6,∀с∈С|c| = 6,\forall c\in C| С|= 32|С|знак равно32|C| = 32d( ся, сJ) ≥ 2 , 1 ≤ i < j ≤...