Логарифмическая система счисления (LNS) — это арифметическая система, иногда используемая для представления вещественных чисел в компьютере и в цифровых аппаратных средствах, особенно в цифровой обработке сигналов.
Теория
В LNS число X {displaystyle X} представлено логарифмом следующим образом:
X → { s , x = log b ( | X | ) } , {displaystyle X ightarrow {s,x=log _{b}(|X|)},}где x {displaystyle x} - его абсолютное значение; s {displaystyle s} обозначающий знак X {displaystyle X} ( s = 0 {displaystyle s=0} если X > 0 {displaystyle X>0} и s = 1 {displaystyle s=1} если X < 0 {displaystyle X<0} ).
Эта формулировка упрощает операции умножения, деления, возведения в степень, так как они сводятся к сложению, вычитанию, умножению и делению, соответственно. С другой стороны, операции сложения и вычитания в такой форме записи оказываются более сложными, и они рассчитываются по формулам:
log b ( | X | + | Y | ) = x + s b ( y − x ) {displaystyle log _{b}(|X|+|Y|)=x+s_{b}(y-x)} log b ( | | X | − | Y | | ) = x + d b ( y − x ) , {displaystyle log _{b}(||X|-|Y||)=x+d_{b}(y-x),}где z = y − x {displaystyle z=y-x} разница между логарифмами операндов, функция «суммы» s b ( z ) = log b ( 1 + b z ) {displaystyle s_{b}(z)=log _{b}(1+b^{z})} , а функция «разницы» d b ( z ) = log b ( | 1 − b z | ) {displaystyle d_{b}(z)=log _{b}(|1-b^{z}|)} . Эти функции s b ( z ) {displaystyle s_{b}(z)} и d b ( z ) {displaystyle d_{b}(z)} , изображенные на рисунке справа, также известны как логарифмы Гаусса. Упрощение умножения, деления, взятия корня и возведения в степень компенсируется сложностью оценки этих функций для сложения и вычитания. Эта добавленная стоимость оценки может быть незначительна при использовании LNS в первую очередь для повышения точности операций с плавающей запятой.
История
Логарифмическая система счисления была независимо изобретена и опубликована по крайней мере три раза, в качестве альтернативы системам счисления с фиксированной и с плавающей запятой.
Кингсбери и Рейнер представили «логарифмическую арифметику» для цифровой обработки сигналов в 1971 году.
Аналогичная LNS была описана в 1975 году Шварцлендером и Алехопоулосом.
Ли и Эдгар описал подобную систему счисления, которую они назвали «Фокус», в 1977 году
Математические основы для сложения и вычитания в LNS восходят к Карлу Фридриху Гауссу и Z. Leonelli.
Применение
LNS была использована в Gravity Pipe (GRAPE) — специальном суперкомпьютере, который выиграл Премию Гордона Белла в 1999 году.
LNS обычно используется как часть скрытых марковских моделей, таких как Алгоритм Витерби, для распознавания речи и секвенирования ДНК.
Значительные усилия в исследовании применимости LNS в качестве жизнеспособной альтернативы системам с плавающей запятой общего назначения для обработки одинарной точности вещественных чисел описаны в контексте «Европейского логарифмического микропроцессора» (ELM). Представлен прототип 32-разрядного процессора, функционирующего в LNS. Дальнейшее совершенствование LNS, основанной на архитектуре ELM вновь показало значительно лучшую скорость вычислений и большую точность, нежели вычисления с плавающей запятой.
LNS иногда используется в FPGA — приложениях, где большинство арифметических операций это умножение и деление.