Битовая кодировка для вектора рациональных чисел

Question

Я хотел бы реализовать сверхкомпактное хранилище для структур с рациональными числами.

В книге Александра Шрайвера "Теория линейного и целочисленного программирования" я нашел определение размеров битов (стр. 15). рациональное число , вектор и матрица:

Представление рационального числа ясно: один бит для знака и логарифм длячастное и дробь.

Я не могу понять, как вектор может быть закодирован только в n битах, чтобы различать его элементы?Например, что если я хотел бы написать вектор из двух элементов: 524 = 1000001100b, 42 = 101010b.Как я могу использовать только 2 дополнительных бита, чтобы указать, когда заканчивается 1000001100 и начинается 101010?

Та же проблема существует с матричным представлением.

Answer 1

Конечно, невозможно просто добавить целочисленные представления друг к другу и добавить информацию о месте слияния, так как это займет гораздо больше битов, чем дано формулой в книге, чего я не делаюиметь доступ к.
Я считаю, что это проблема из теории кодирования, где я не эксперт.Но я нашел то, что могло бы указать вам правильное направление.В этом посте описан «интерполяционный код» среди других.Если вы примените его к своему примеру (524, 42), вы получите
f (число целых чисел, которые должны быть закодированы, все в диапазоне [1, N] = 2
N = 524
максимумдлина битов кодированных 2 целых чисел тогда равна
f • (2,58 + log (N / f)) = 9,99…, т.е. 10 бит
Таким образом, возможно иметь ультракомпактное кодирование, хотя на кодирование и декодирование приходилось тратить много времени.

Answer 2

Невозможно использовать только два бита, чтобы указать, когда конечный конец и дробь начинаются.По крайней мере, вам понадобится длина, равная длине частного или / и длине размера дроби.Другой способ - использовать фиксированное число битов как для частного, так и для дробного числа, аналогичного IEEE 754 .