Логарифмическая система счисления

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Функции:. s_b(z) и d_b(z)

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

Теория[править | править вики-текст]

В LNS число X представлено логарифмом следующим образом:

X\rightarrow\{s,x=\log_b(|X|)\},

, где x, его абсолютное значение; s обозначающий знак X (s=0 если X>0 и s=1 если X<0).

Эта формулировка упрощает операции умножения, деления, возведение в степень и корни, так как они снижены до сложения, вычитания, умножения и деления, соответственно. С другой стороны, операции сложения и вычитания являются более сложными, и они рассчитываются по формулам:

\log_b(|X|+|Y|)=x+s_b(z)
 \log_b(||X|-|Y||)=x+d_b(z),

где z=y-x разница между логарифмами операндов, «сумма» функции s_b(z)=\log_b(1+b^z), а «разница» функции d_b(z)=\log_b(|1-b^z|). Эти функции s_b(z) и d_b(z), изображенные на рисунке справа, также известны как логарифмы Гаусса. Упрощение умножения, деления, взятия корня и возведения в степень компенсируется сложностью оценки этих функций для сложения и вычитания. Эта добавленная стоимость оценки может быть важна при использовании LNS в первую очередь для повышения точности операций с плавающей точкой математике.

История[править | править вики-текст]

Логарифмическая система счисления была независимо изобретена и опубликована по крайней мере три раза, в качестве альтернативы системам счисления с фиксированной и с плавающей точкой.[1]

Кингсбери и Рейнер представили «логарифмическую арифметику» для цифровой обработки сигналов в 1971 году.[2]

Аналогичная LNS была описана в 1975 году Шварцлендером и Алехопоулосом.[3]

Ли и Эдгар описал подобную систему счисления, которую они назвали «Фокус», в 1977 году[4]

Математические основы для сложения и вычитания в LNS восходят к Карлу Фридриху Гауссу и Z. Leonelli.[5][6]

Применение[править | править вики-текст]

LNS была использована в Gravity Pipe (GRAPE) специальном суперкомпьютере[7] который выиграл Премию Гордона Белла в 1999 году. LNS обычно используется как часть скрытых марковских моделей, таких как Алгоритм Витерби, для распознавании речи и секвенирования ДНК.

Значительные усилия, в исследовании применимости LNS в качестве жизнеспособной альтернативы системам с плавающей точкой общего назначения для обработки одинарной точности вещественных чисел описаны в контексте европейской Логарифмическая микропроцессорных систем (ELM).[8] Представлен прототип процессора, который имеет 32-разрядную котрансформацию на основе LNS. Дальнейшее совершенствование LNS, основанной на архитектуре ELM вновь показало значительно лучшую скорость вычислений и большую точность, нежели вычисления с плавающей точкой.[9]

LNS иногда используется в FPGA — приложениях, где большинство арифметических операций это умножение и деление.[10]

Примечания[править | править вики-текст]

  1. S. C. Lee and A. D. Edgar (Sept. 1979). «Addendum to "The Focus Number System"». IEEE Transactions on Computers C-28 (9): 693. DOI:10.1109/TC.1979.1675442.
  2. N. G. Kingsburg and P. J. W. Rayner (Jan. 28, 1971). «Digital filtering using logarithmic arithmetic». Electronics Letters 7: 55.
  3. E. E. Swartzlander and A. G. Alexopoulos (December 1975). «The Sign/Logarithm Number System». IEEE Transactions on Computers C-24 (12): 1238–1242. DOI:10.1109/T-C.1975.224172.
  4. S. C. Lee and A. D. Edgar (Nov. 1977). «The focus number system». IEEE Transactions on Computers C-26 (11): 1167–1170. DOI:10.1109/TC.1977.1674770.
  5. Logarithm: Addition and Subtraction, or Gaussian Logarithms. Encyclopædia Britannica Eleventh Edition. Архивировано из первоисточника 29 января 2013.
  6. G. Waldo Dunnington Carl Friedrich Gauss. — MAA, 2002. — ISBN 0-88385-547-X
  7. J Makino and M. Taiji Scientific Simulations with Special Purpose Computers: The GRAPE Systems. — Wiley, 1998. — ISBN 978-0-471-96946-4
  8. J. N. Coleman, C. I. Softley, J. Kadlec, R. Matousek, M. Tichy, Z. Pohl, A. Hermanek, and N. F. Benschop (April 2008). «The European Logarithmic Microprocessor». IEEE Transactions on Computers 57 (4): 532–546. DOI:10.1109/TC.2007.70791.
  9. R.C Ismail and J.N Coleman (July 2011). «ROM-less LNS». 2011 20th IEEE Symposium on Computer Arithmetic (ARITH): 43–51. DOI:10.1109/ARITH.2011.15.
  10. Haohuan Fu, Oskar Mencer, Wayne Luk (June 2010). «Comparing Floating-point and Logarithmic Number Representations for Reconfigurable Acceleration». IEEE Conference on Field Programmable Technology: 337. DOI:10.1109/FPT.2006.270342.

Ссылки[править | править вики-текст]