Есть ли способ использовать полубиты?

19

Как известно большинству людей, используя 4 бита, мы можем считать от 0 до 15 (0123456789ABCDEF в шестнадцатеричном формате). Но если бы мы считали только до 9, мы все равно использовали бы 4 бита, и цифры от A до F были бы потрачены впустую.

Однако на странице QR-кода в Википедии говорится, что при использовании только цифровых цифр от 0 до 9 используется 3 9 бит на символ, что является правильным с точки зрения статистики. И все же треть бита не является физическим объектом, и отправка числа от 0 до 9 использует, по крайней мере, 4 бита, насколько мне известно.

Есть ли способ использовать потраченные впустую комбинации для эффективной отправки символа с долями битов?

Хорошо, позвольте мне привести пример: две цифры «27» должны быть отправлены. При нормальных методах кодирования отправленные биты были бы 00100111. Затем мы могли бы представить систему, которая заменит цифру «2» на цифру «E» или «F», в зависимости от следующего бита; в этом случае следующий бит равен 0, поэтому «2» заменяется на «E». Результирующая битовая строка будет тогда иметь вид 1101 0 111. С другой стороны, если цифры «28» должны быть отправлены, первый бит после «2» будет 1, поэтому вместо этого он заменяется цифрой «F», получая строку 1111 1 000.

В обоих случаях была достигнута экономия в 1 бит, потому что один клев использовался для двух разных символов. Другими словами, три с половиной бита используются для каждого символа.

Galahad78
источник
2
Чтобы по-другому взглянуть на упаковку значений в меньшем цифровом пространстве, ознакомьтесь с троичными компьютерами ( en.wikipedia.org/wiki/Ternary_computer ). Если для Кнута этого достаточно, то для меня этого достаточно!
RLH
3
Еще лучше признать, что вы можете вычислить (10 * first_digit) + second_digitи закодировать это в 7 битов, представляющих 0 ... 99, с кодами 100-127, оставленными для других целей. И еще больше экономии благодаря 3 цифрам, сжатым в 10 бит.
Hot Licks
Чтобы отправить все 100 различных значений по отдельности, лучшее, что вы можете получить, - это упаковка в 7 бит. Если у вас есть больше цифр, упаковка будет более эффективной. Если у вас есть менее 64 значений для отправки, вы можете отправить его, используя только 6 битов
phuclv

Ответы:

22

Вы не можете отправить половину бита, но вы можете эффективно упаковать две половины бита в один бит перед передачей или хранением.

Вы сами приводите пример, поэтому фактически ответили на свой вопрос ДА.

Возможно, несколько более простой способ заключается в простом кодировании значения двух десятичных цифр в 7 бит. (Вид двоичного кода с двойным десятичным знаком).

Воутер ван Оойен
источник
1
Один хороший пример использования для упаковки пар цифр в семь бит - это передача файлов ASCII, которые состоят в основном из числовых данных. Любое значение байта ниже 128 представляет один символ ASCII, в то время как 128-227 представляют две цифры ASCII. Легко кодировать или декодировать, и не требует, чтобы данные содержали в основном цифры (или даже любые цифры), но может очень легко сжимать строки цифр на 50%.
суперкат
Или тот формат PDP11, в котором 3 буквенно-цифровых символа упакованы в 16 бит с одним запасным битом ...
Брайан Драммонд,
@BrianDrummond: 16 бит можно использовать для хранения ровно трех символов из набора 40 или до трех из набора 39, но запасного бита не будет. Обычно «алфавитно-цифровой» подразумевает набор по меньшей мере из 36, но единственным вариантом будет резервный бит, если набор будет ограничен 32.
суперкат
Я думал, что это было 5 бит / символ. Буквенно-цифровой код был разбит на два набора кодов, причем один символ зарезервирован для «набора кодов коммутатора» Я был не прав: en.wikipedia.org/wiki/DEC_Radix-50 Впрочем, как ни странно, он увидел это только однажды ночью, когда мне пришлось декодировать отчет, который мне дали на 8 "дискете, в системе CP / M, только с тусклым светом воспоминание о Z80 asm.
Брайан Драммонд
19

Вы можете использовать кодирование Хаффмана, чтобы числа имели различную длину в битах. если вам известна цифра, которая встречается чаще других, это поможет.

пример (с одинаковым вхождением):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

пример получения для получения номера 1:

Первый бит входит и оставляет только от 0 до 4 в качестве параметров.

второй бит входит и оставляет только от 0 до 2 в качестве параметров.

третий бит входит и оставляет от 0 до 1 в качестве параметров.

четвертый бит поступает, и входящий номер равен 1

markg
источник
12

Возможно, то, что вы ищете, - это арифметическое кодирование, которое может эффективно кодировать строку символов, каждый из которых в принципе может потребовать дробного (нецелого) числа битов. (хотя общее сообщение должно быть целым числом битов)

Цитируя Википедию :

Арифметическое кодирование отличается от других форм энтропийного кодирования, таких как кодирование Хаффмана, тем, что вместо разделения входных данных на составляющие символы и замены каждого из них на код, арифметическое кодирование кодирует все сообщение в одно число, дробь n где (0,0 ≤ n < 1.0).

Хью Аллен
источник
10

Новый IEEE P754 для арифметики с плавающей запятой теперь определяет десятичные форматы в дополнение к двоичному. В одном из кодировок предлагается группировать цифровые цифры по 3 в 10 бит.

кодирование от 0 до 999 с использованием 10 битов = 1024 возможных кодов является достаточно эффективным, и десятичные цифры часто так или иначе группируются по трем.

Плотно упакованный десятичный знак : http://en.wikipedia.org/wiki/Densely_packed_decimal

TEMLIB
источник
Даже если десятичные цифры сгруппированы по трем, для правильной семантики десятичных чисел с плавающей точкой может потребоваться, чтобы (1) масштабирование мантиссы степенью не кратной трем десяти означало умножение или деление всех составляющих на 10 или 100; (2) некоторые биты могут использоваться как для верхней, так и для нижней части числа, в зависимости от (показатель степени 3); (3) Если показатель степени хранится в base-1000, то иногда может быть необходимо округлить нижнюю группу из трех цифр до ближайших 10 или ближайших 100, а не до ближайшей единицы.
суперкат
Я лично считаю, что типы вроде BigDecimalбы для многих целей были бы более эффективными, если бы каждое слово содержало 9 десятичных цифр, а не 32 бита, но группирование цифр не должно влиять на поведение округления.
суперкат
4

Двоичное (или шестнадцатеричное) соответствие 1: 1 - это всего лишь один символ, кодирующий биты. Так что да, как вы показали, это возможно. Другое место, где это используется, - (но немного по-другому) - решетчатое кодирование / декодирование в системах связи, в которых переходы битов хранятся дальше друг от друга, чтобы облегчить декодирование. И, конечно, кодирование 8b / 10b и 64b / 66b и т. Д. И т. Д. Является аналогичной идеей, в которой меньшее пространство символов кодируется в немного избыточном большем пространстве для получения баланса постоянного тока, разделения символов и кодов управления в подполосах.

заполнитель
источник
4

Представление данных зависит от интерпретации, которую вы или ваша программа дает ему.

Мы могли бы отправить «27» также в виде символов ASCII, например, в качестве результата 0x3237 = 0b0011001000110111.

xn(x)log2n(x)

x1,x2n(x1),n(x2)log2n(x1)+log2n(x2)log2(n(x1)n(x2))

2log2(10)=24=8log2(1010)=7

Это всегда зависит от приложения, но обычно, когда вы «объединяете» переменные, как вы предлагаете, это потребует больших вычислительных ресурсов, если вы захотите выполнить операции с этими переменными. Сложение и вычитание операций над «объединенными» переменными более сложны, чем обычно, и могут потребовать больше места в аппаратном обеспечении или вызвать более длительные задержки.



источник
2

Обычный способ упаковки значений заключается в умножении каждого значения на его диапазон, так что в итоге получается одно большое число, которое вы можете эффективно представить в битах. При распаковке вы делите на диапазон, остаток - это цифра, а результат - оставшиеся упакованные цифры.

Если у вас есть 5 значений в диапазоне от 0 до 2, вы можете представить это в 8 битах (для представления значений необходимо не менее 7,92 битов) вместо 10 битов, используемых наивным способом использования 2 битов для каждого значения, выполняя (((n 1 * 3 + n 2 ) * 3 + n 3 ) * 3 + n 4 ) * 3 + n 5

Ринзе Смитс
источник
Есть ли название для этого метода кодирования?
Киган Джей
1

Теоретически, если вы готовы тратить пространство схемы и мощность на детектор с высоким импедансом, вы можете отправить 3 состояния по цифровому проводу (1, 0 и высокий Z). Отказ от ответственности: это прекрасно работает в симуляторе. Я не знаю, есть ли у схемы какие-то проблемы, которые делают ее непрактичной, например, сказать, что она не может переключаться так же быстро, как обычная пара ворот.

Мой обычный термин для перехода сигнала от высокого Z к сигналу (где сигнал обычно заземлен в кремнии) - это полуразрядный сигнал.

Джошуа
источник
1

Вы хотите отправить одну десятичную цифру, требующую 3⅓ бит. Но вам придется использовать 4 бита, потому что вы не можете отправить треть бита.

Итак, чтобы узнать, что на самом деле означает 3⅓ бит, вам нужно две (или три) цифры по 3⅓ бита каждая. Если вы хотите отправить 2 (3) десятичные цифры от 0 до 9, каждая из которых требует чуть менее 3 less бит, вы можете сделать это, используя 7 (10) бит. Конструктивное доказательство легко:

7 (10) бит позволяют вам кодировать число от 0 до 128 (1023), но вам понадобятся только от 00 (000) до 99 (999), которые представляют собой все возможные кодировки из двух (трех) десятичных цифр. QED

Александр
источник
1

Я думаю, что вы неправильно понимаете, что подразумевается в связанной вики-статье. Что имеется в виду , что для строки символов, которая полностью числовая (без пробелов, запятых или периодов), используя идеальную компрессию, вы можете представлять каждый символ , используя 3 +1 / 3 бита в среднем . На самом деле, это немного лучше, чем это, поскольку математика говорит, что вы можете получить log 2 (10) = 3.3219 бит / символ в долгосрочной перспективе.

Аналогичным образом, для набора буквенно-цифровых символов плюс некоторые символы (только заглавные буквы и 9 символов) или 45 символов требуется лог 2 (45) = 5,4918 бит / символ, что в статье округлено до 5,5.

Уменьшенные биты / символ достигаются с помощью сжатия, либо с предварительно заданным кодированием, либо со схемой сжатия, определенной стандартом QR (я не уверен, какой из них используется). Он представляет собой среднее число битов, которое потребуется символу для кодирования, поэтому отдельный символ будет кодироваться с использованием большего или меньшего количества битов. Также осознайте, что значения, перечисленные выше, являются идеальными значениями для бесконечных случайных строк. Можно получить коэффициенты сжатия, которые лучше или хуже для специально созданных строк.

MBraedley
источник