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

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

Обзор

Число, $X$ , представлена в ЛНС двумя компонентами: логарифмом ( $x$ ) его абсолютного значения (как двоичное слово, обычно в дополнении до двух ) и его знакового бита ( $s$ ):

X\rightarrow {\begin{cases}x=\log _{b}{\big |}X{\big |}\,,\\s={\begin{cases}0{\text{ if }}X>0\,,\\1{\text{ if }}X<0\,.\end{cases}}\end{cases}}

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

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

\log _{b}(|X|+|Y|)=x+s_{b}(y-x)\,,

\log _{b}{\bigg |}|X|-|Y|{\bigg |}=x+d_{b}(y-x)\,,

где функция «сумма» определяется выражением $s_{b}(z)=\log _{b}(1+b^{z})$ и функция «разности» по $d_{b}(z)=\log _{b}{\big |}1-b^{z}{\big |}$ . Эти функции $s_{b}(z)$ и $d_{b}(z)$ также известны как гауссовы логарифмы .

Упрощение умножения, деления, получения корней и степеней уравновешивается стоимостью оценки этих функций на сложение и вычитание. Эта дополнительная стоимость оценки может не иметь решающего значения при использовании LNS в первую очередь для повышения точности математических операций с плавающей запятой.

История

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

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

Похожая LNS, названная «знаково-логарифмическая система счисления» (SLNS), была описана в 1975 году Эрлом Шварцландером и Аристидесом Алексопулосом ; вместо того, чтобы использовать обозначение дополнения до двух для логарифмов, они смещают их (масштабируют представляемые числа), чтобы избежать отрицательных журналов. ^[3]

Сэмюэл Ли и Альберт Эдгар описали аналогичную систему, которую они назвали системой счисления «Фокус», в 1977 году. ^[4]^[1]^[5]^[6]

Математические основы сложения и вычитания в LNS восходят к Зеккини Леонелли и Карлу Фридриху Гауссу в начале 1800-х годов. ^[7]^[8]^[9]^[10]^[11]

Приложения

В конце 1800-х годов испанский инженер Леонардо Торрес Кеведо задумал серию аналоговых вычислительных механических машин. ^[12]^[13] и разработал систему, которая могла решать алгебраические уравнения с восемью членами, находя корни, в том числе комплексные. Одна часть этой машины, называемая «бесконечным шпинделем», позволяла механически выразить соотношение $y=\log(1+10^{x})$ , ^[14] с целью извлечения логарифма суммы как суммы логарифмов.

ЛНС использована в Gravity Pipe (Gravity Pipe ( GRAPE-5 )). суперкомпьютере специального назначения ^[15] который выиграл премию Гордона Белла в 1999 году.

Значительные усилия по изучению применимости LNS в качестве жизнеспособной альтернативы плавающей запятой для универсальной обработки действительных чисел одинарной точности описаны в контексте Европейского логарифмического микропроцессора (ELM). ^[16]^[17] Изготовленный прототип процессора, который имеет 32-битное арифметико-логическое устройство LNS (ALU), основанное на совместном преобразовании, продемонстрировал LNS как «более точную альтернативу операциям с плавающей запятой» с улучшенной скоростью. Дальнейшее усовершенствование конструкции LNS на основе архитектуры ELM показало ее способность обеспечивать значительно более высокую скорость и точность, чем операции с плавающей запятой. ^[18]

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

См. также

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Ли, Сэмюэл К.; Эдгар, Альберт Д. (сентябрь 1979 г.). «Дополнение к «Системе чисел Фокуса» ». Транзакции IEEE на компьютерах . С-28 (9). IEEE : 693. doi : 10.1109/TC.1979.1675442 . ISSN 0018-9340 . (Обратите внимание: имя Николаса Кингсбери в этой цитате написано неправильно.)
^ Кингсбери, Николас Г.; Рейнер, Питер Дж.В. (28 января 1971 г.). «Цифровая фильтрация с использованием логарифмической арифметики» . Электронные письма . 7 (2). Инженерно-технологический институт (ИЭТ): 56–58. дои : 10.1049/эл:19710039 . ISSN 0013-5194 . Также перепечатано в: Шварцландер-младший, Эрл Э., изд. (1990). Компьютерная арифметика . Том. И. Лос Аламитос, Калифорния, США: Издательство IEEE Computer Society Press .
^ Шварцландер-младший, Эрл Э.; Алексопулос, Аристидес Георгиу (декабрь 1975 г.). «Знаково-логарифмическая система счисления». Транзакции IEEE на компьютерах . С-24 (12). IEEE : 1238–1242. дои : 10.1109/TC.1975.224172 . ISSN 0018-9340 . Также перепечатано в: Шварцландер-младший, Эрл Э., изд. (1990). Компьютерная арифметика . Том. И. Лос Аламитос, Калифорния, США: Издательство IEEE Computer Society Press .
^ Ли, Сэмюэл К.; Эдгар, Альберт Д. (ноябрь 1977 г.). «Система чисел фокуса». Транзакции IEEE на компьютерах . С-26 (11). IEEE : 1167–1170. дои : 10.1109/TC.1977.1674770 . ISSN 0018-9340 .
^ Ли, Сэмюэл К.; Эдгар, Альберт Д. (1977). «Глава I.1.: Проектирование микрокомпьютера – система счисления микрокомпьютера» . В Ли, Сэмюэл К. (ред.). Проектирование и применение микрокомпьютеров . Academic Press, Inc., стр. 1–40. дои : 10.1016/B978-0-12-442350-3.50005-5 . ISBN 0-12-442350-7 . [1]
^ Эдгар, Альберт Д.; Ли, Сэмюэл К. (март 1979 г.). «Система счисления микрокомпьютера ФОКУС» . Коммуникации АКМ . 22 (3). ACM Press : 166–177. дои : 10.1145/359080.359085 .
^ Леонелли, Зеккини (1803) [1802]. Логарифмическое дополнение. Теория дополнительных и дидуктивных логарифмов (на французском языке). Бордо: Броссье. (Примечание: 1802/1803 — это XI год по французскому республиканскому календарю .)
^ Леонарди, Готфрид Вильгельм (1806). Логарифмические дополнения ЛЕОНЕЛЛИ как вклад в восполнение недостатков обычных логарифмических таблиц. Перевод с французского с некоторыми дополнениями ГОТФРИДА ВИЛЬГЕЛЬМА ЛЕОНХАРДИ, младшего лейтенанта избирательного саксонского корпуса полевой артиллерии (на немецком языке). Дрезден: Walther'sche Hofbuchhandlung. Зеккини Леонелли (Примечание. Расширенный перевод « Supplement logarithmique. Théorie des logarithmes addels et diductifs» .)
^ Гаусс, Иоганн Карл Фридрих (12 февраля 1808 г.). «ЛЕОНЕЛЛИ, Логарифмические добавки». Общая литературная газета (на немецком языке) (45). Галле-Лейпциг: 353–356.
^ «Логарифм: сложение и вычитание, или Гауссовы логарифмы» . Британская энциклопедия, одиннадцатое издание .
^ Даннингтон, Гай Уолдо (2004) [1955]. Грей, Джереми; Дозе, Фриц-Эгберт (ред.). Карл Фридрих Гаусс – Титан науки . Серия «Спектр» (переработанная ред.). Математическая ассоциация Америки (МАА). ISBN 978-0-88385-547-8 .
^ Хорсбург, Эллис Мартин (1914). « Инструментальное решение числовых уравнений , Д. Гибб, Массачусетс» . Написано на выставке, посвященной 300-летию Нейпира. Современные инструменты и методы расчета: справочник Трехсотлетней выставки Нейпира . Герштейн – Университет Торонто. Лондон, Великобритания: Дж. Белл. п. 263.
^ Мемке, Рудольф [на немецком языке] (1908). «И23». Энциклопедия чистых и прикладных математических наук . Париж, Франция: Готье-Виллар. п. 351.
^ Ф. Томас. Краткий отчет о «Бесконечном шпинделе» Леонардо Торреса , «Механизм и теория машин», Том. 43, № 8, стр. 1055-1063, 2008.
^ Макино, Дзюнъитиро; Тайдзи, Макото (1998). Научное моделирование с помощью компьютеров специального назначения: системы GRAPE . Джон Уайли и сыновья . Бибкод : 1998sssc.book.....M . ISBN 978-0-471-96946-4 .
^ Коулман, Джон Николас; Софтли, Кристофер И.; Кадлец, Иржи; Матоусек, Рудольф; Личко, Мирослав; Поль, Зденек; Германек, Антонин (7 августа 2002 г.) [04 ноября 2001 г.]. «Европейский логарифмический микропроцессор - приложение QR RLS». Протокол конференции тридцать пятой асиломарской конференции по сигналам, системам и компьютерам (кат. № 01CH37256) . Том. 1. Монтерей, Калифорния, США: IEEE . стр. 155–159. дои : 10.1109/ACSSC.2001.986897 . ISBN 0-7803-7147-Х . ISSN 1058-6393 .
^ Коулман, Джон Николас; Софтли, Кристофер И.; Кадлец, Иржи; Матоусек, Рудольф; Тичи, Милан; Поль, Зденек; Германек, Антонин; Беншоп, Нико Ф. (апрель 2008 г.) [26 февраля 2008 г.]. «Европейский логарифмический микропроцессор». Транзакции IEEE на компьютерах . 57 (4). IEEE : 532–546. дои : 10.1109/TC.2007.70791 . ISSN 0018-9340 .
^ Исмаил, Р. Че; Коулман, Джон Николас (18 августа 2011 г.) [25 июля 2011 г.]. «БезПЗУ LNS». 20-й симпозиум IEEE по компьютерной арифметике , 2011 г. ИИЭЭ . стр. 43–51. дои : 10.1109/ARITH.2011.15 . ISBN 978-1-4244-9457-6 . ISSN 1063-6889 .
^ Фу, Хаохуань; Менсер, Оскар; Люк, Уэйн (2 января 2007 г.) [13 декабря 2006 г.]. «Сравнение представлений чисел с плавающей запятой и логарифмических чисел для реконфигурируемого ускорения». 2006 Международная конференция IEEE по программируемым технологиям . ИИЭЭ . стр. 337–340. дои : 10.1109/FPT.2006.270342 . ISBN 978-0-7803-9728-6 .

Дальнейшее чтение

Мюллер, Жан-Мишель; Щербина, Александр; Тиссеран, Арно (февраль 1998 г.). «Полулогарифмические системы счисления» (PDF) . Транзакции IEEE на компьютерах . 47 (2): 145–151. дои : 10.1109/12.663760 . ISSN 0018-9340 . Архивировано (PDF) из оригинала 13 июля 2018 г. Проверено 11 июля 2018 г. Ранее опубликовано в: Мюллер, Жан-Мишель; Щербина, Александр; Тиссеран, Арно (июль 1995 г.). «Полулогарифмические системы счисления». Труды 12-го симпозиума IEEE по компьютерной арифметике ( ARITH 12 ) . Бат, Великобритания.
Карс, Марк; Бранденбург, Карлхайнц, ред. (2002) [1998]. Применение цифровой обработки сигналов в аудио и акустике (PDF) . Академическое издательство Клювер . ISBN 0-7923-8130-0 . Архивировано (PDF) из оригинала 7 июля 2018 г. Проверено 7 июля 2018 г. (Примечание. Описывается 13-битный LNS, использовавшийся в Yamaha музыкальных синтезаторах в 1980-х годах.)
Кремер, Герман (29 августа 2002 г.). «Логарифам гауссовского сложения исполняется 200 лет» . de.sci.mathematik (на немецком языке). Архивировано из оригинала 7 июля 2018 г. Проверено 7 июля 2018 г.
Ценднер, Эберхард (лето 2008 г.). «Компьютерная арифметика: логарифмические системы счисления» (PDF) (сценарий лекции) (на немецком языке). Йенский университет имени Фридриха Шиллера . Архивировано (PDF) из оригинала 9 июля 2018 г. Проверено 9 июля 2018 г. [2]
Хейс, Брайан (сентябрь – октябрь 2009 г.). «Высшая арифметика» . Американский учёный . 97 (5): 364–368. дои : 10.1511/2009.80.364 . Архивировано из оригинала 9 июля 2018 г. Проверено 9 июля 2018 г. [3] . Также перепечатано в: Хейс, Брайан (2017). «Глава 8: Высшая арифметика». Защита от дурака и другие математические размышления (1-е изд.). Массачусетский технологический институт Пресс . стр. 113–126. ISBN 978-0-26203686-3 . ISBN 0-26203686-X .
Амир Саббаг, Молахоссейни; де Соуза, Леонель Сибра; Чип-Хонг Чанг, ред. (21 марта 2017 г.). Проектирование встраиваемых систем с использованием специальной арифметики и систем счисления (1-е изд.). Спрингер Интернэшнл Паблишинг АГ . дои : 10.1007/978-3-319-49742-6 . ISBN 978-3-319-49741-9 . LCCN 2017934074 . (389 страниц)

Внешние ссылки

[Lee_1979_1-1] Jump up to: Перейти обратно: ^а ^б Ли, Сэмюэл К.; Эдгар, Альберт Д. (сентябрь 1979 г.). «Дополнение к «Системе чисел Фокуса» ». Транзакции IEEE на компьютерах . С-28 (9). IEEE : 693. doi : 10.1109/TC.1979.1675442 . ISSN 0018-9340 . (Обратите внимание: имя Николаса Кингсбери в этой цитате написано неправильно.)

[Kingsbury_1971-2] Кингсбери, Николас Г.; Рейнер, Питер Дж.В. (28 января 1971 г.). «Цифровая фильтрация с использованием логарифмической арифметики» . Электронные письма . 7 (2). Инженерно-технологический институт (ИЭТ): 56–58. дои : 10.1049/эл:19710039 . ISSN 0013-5194 . Также перепечатано в: Шварцландер-младший, Эрл Э., изд. (1990). Компьютерная арифметика . Том. И. Лос Аламитос, Калифорния, США: Издательство IEEE Computer Society Press .

[Swartzlander_1975-3] Шварцландер-младший, Эрл Э.; Алексопулос, Аристидес Георгиу (декабрь 1975 г.). «Знаково-логарифмическая система счисления». Транзакции IEEE на компьютерах . С-24 (12). IEEE : 1238–1242. дои : 10.1109/TC.1975.224172 . ISSN 0018-9340 . Также перепечатано в: Шварцландер-младший, Эрл Э., изд. (1990). Компьютерная арифметика . Том. И. Лос Аламитос, Калифорния, США: Издательство IEEE Computer Society Press .

[Lee_1977_1-4] Ли, Сэмюэл К.; Эдгар, Альберт Д. (ноябрь 1977 г.). «Система чисел фокуса». Транзакции IEEE на компьютерах . С-26 (11). IEEE : 1167–1170. дои : 10.1109/TC.1977.1674770 . ISSN 0018-9340 .

[Lee_1977_2-5] Ли, Сэмюэл К.; Эдгар, Альберт Д. (1977). «Глава I.1.: Проектирование микрокомпьютера – система счисления микрокомпьютера» . В Ли, Сэмюэл К. (ред.). Проектирование и применение микрокомпьютеров . Academic Press, Inc., стр. 1–40. дои : 10.1016/B978-0-12-442350-3.50005-5 . ISBN 0-12-442350-7 . [1]

[Lee_1979_2-6] Эдгар, Альберт Д.; Ли, Сэмюэл К. (март 1979 г.). «Система счисления микрокомпьютера ФОКУС» . Коммуникации АКМ . 22 (3). ACM Press : 166–177. дои : 10.1145/359080.359085 .

[Leonelli_1802-7] Леонелли, Зеккини (1803) [1802]. Логарифмическое дополнение. Теория дополнительных и дидуктивных логарифмов (на французском языке). Бордо: Броссье. (Примечание: 1802/1803 — это XI год по французскому республиканскому календарю .)

[Leonhardi_1806-8] Леонарди, Готфрид Вильгельм (1806). Логарифмические дополнения ЛЕОНЕЛЛИ как вклад в восполнение недостатков обычных логарифмических таблиц. Перевод с французского с некоторыми дополнениями ГОТФРИДА ВИЛЬГЕЛЬМА ЛЕОНХАРДИ, младшего лейтенанта избирательного саксонского корпуса полевой артиллерии (на немецком языке). Дрезден: Walther'sche Hofbuchhandlung. Зеккини Леонелли (Примечание. Расширенный перевод « Supplement logarithmique. Théorie des logarithmes addels et diductifs» .)

[Gauss_1808-9] Гаусс, Иоганн Карл Фридрих (12 февраля 1808 г.). «ЛЕОНЕЛЛИ, Логарифмические добавки». Общая литературная газета (на немецком языке) (45). Галле-Лейпциг: 353–356.

[Theodora-10] «Логарифм: сложение и вычитание, или Гауссовы логарифмы» . Британская энциклопедия, одиннадцатое издание .

[Dunnington_2004-11] Даннингтон, Гай Уолдо (2004) [1955]. Грей, Джереми; Дозе, Фриц-Эгберт (ред.). Карл Фридрих Гаусс – Титан науки . Серия «Спектр» (переработанная ред.). Математическая ассоциация Америки (МАА). ISBN 978-0-88385-547-8 .

[Horsburg-Napier_1914-12] Хорсбург, Эллис Мартин (1914). « Инструментальное решение числовых уравнений , Д. Гибб, Массачусетс» . Написано на выставке, посвященной 300-летию Нейпира. Современные инструменты и методы расчета: справочник Трехсотлетней выставки Нейпира . Герштейн – Университет Торонто. Лондон, Великобритания: Дж. Белл. п. 263.

[Mehmke_1908-13] Мемке, Рудольф [на немецком языке] (1908). «И23». Энциклопедия чистых и прикладных математических наук . Париж, Франция: Готье-Виллар. п. 351.

[Thomas2008-14] Ф. Томас. Краткий отчет о «Бесконечном шпинделе» Леонардо Торреса , «Механизм и теория машин», Том. 43, № 8, стр. 1055-1063, 2008.

[Makino_1998-15] Макино, Дзюнъитиро; Тайдзи, Макото (1998). Научное моделирование с помощью компьютеров специального назначения: системы GRAPE . Джон Уайли и сыновья . Бибкод : 1998sssc.book.....M . ISBN 978-0-471-96946-4 .

[Coleman_2001-16] Коулман, Джон Николас; Софтли, Кристофер И.; Кадлец, Иржи; Матоусек, Рудольф; Личко, Мирослав; Поль, Зденек; Германек, Антонин (7 августа 2002 г.) [04 ноября 2001 г.]. «Европейский логарифмический микропроцессор - приложение QR RLS». Протокол конференции тридцать пятой асиломарской конференции по сигналам, системам и компьютерам (кат. № 01CH37256) . Том. 1. Монтерей, Калифорния, США: IEEE . стр. 155–159. дои : 10.1109/ACSSC.2001.986897 . ISBN 0-7803-7147-Х . ISSN 1058-6393 .

[Coleman_2008-17] Коулман, Джон Николас; Софтли, Кристофер И.; Кадлец, Иржи; Матоусек, Рудольф; Тичи, Милан; Поль, Зденек; Германек, Антонин; Беншоп, Нико Ф. (апрель 2008 г.) [26 февраля 2008 г.]. «Европейский логарифмический микропроцессор». Транзакции IEEE на компьютерах . 57 (4). IEEE : 532–546. дои : 10.1109/TC.2007.70791 . ISSN 0018-9340 .

[Ismail_2011-18] Исмаил, Р. Че; Коулман, Джон Николас (18 августа 2011 г.) [25 июля 2011 г.]. «БезПЗУ LNS». 20-й симпозиум IEEE по компьютерной арифметике , 2011 г. ИИЭЭ . стр. 43–51. дои : 10.1109/ARITH.2011.15 . ISBN 978-1-4244-9457-6 . ISSN 1063-6889 .

[Fu_2006-19] Фу, Хаохуань; Менсер, Оскар; Люк, Уэйн (2 января 2007 г.) [13 декабря 2006 г.]. «Сравнение представлений чисел с плавающей запятой и логарифмических чисел для реконфигурируемого ускорения». 2006 Международная конференция IEEE по программируемым технологиям . ИИЭЭ . стр. 337–340. дои : 10.1109/FPT.2006.270342 . ISBN 978-0-7803-9728-6 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]