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

Abstract

В статье вводятся и исследуются новые системы параллельной машинной арифметики, связанной с представлением данных в избыточной системе счисления с базисом, формируемым последовательностями степеней корней характеристического полинома рекуррентности второго порядка. Такие системы счисления являются модулярными редукциями обобщений системы счисления Дж. Бергмана с основанием, равным «золотому сечению». Описывается ассоциированная система остаточных классов. В качестве приложения к задачам цифровой обработки сигналов в работе предлагается, в частности, новый «безошибочный» алгоритм вычисления дискретной циклической свёртки. Алгоритм основан на применении нового класса дискретных ортогональных преобразований, для которых существуют эффективные реализации, не использующие умножений.