Результат интеллектуальной деятельности: Генератор цифрового белого гауссовского шума по методу Уоллеса

Предлагаемое устройство относится к области электротехники, в частности к устройству моделирования канала связи для проверки модуля помехоустойчивого кодирования.

Естественным путем реализации алгоритма помехоустойчивого кодирования является следующая последовательность действий:

1) Моделирование алгоритма на языке высокого уровня (C – C++, Matlab, Octave, SystemC, OpenCL) причем в целых числах.

2) Реализация алгоритма на ПЛИС (программируемая логическая интегральная схема) [Стешенко В. Б. ПЛИС фирмы Altera: Проектирование устройств обработки сигнала, Москва 2000], представляющей собой набор логических элементов на плате с возможностью их программно коммутировать. Описание алгоритма в этом случае состоит из статического описания коммутации элементов и динамического описания их взаимодействия (VHDL, Verilog). Здесь уже помимо правильности реализации алгоритма встают вопросы энергопотребления и физического быстродействия. На каждый элемент дизайна подается синхроимпульс, обеспечивающий его динамическое взаимодействие с остальными, причем сам элемент имеет емкость и/или индуктивность коммутирующая линия также имеет активное и реактивное сопротивление, которое растет с размерами дизайна, что вынуждает увеличивать напряжение питания с целью предотвратить “размывание” фронтов синхронизирующих импульсов. Все выше изложенные факторы ограничивают тактовую частоту ПЛИС 200 МГц. В настоящее время идут попытки использовать язык высокого уровня для программирования ПЛИС, что осложняется тем фактом, что языки высокого уровня не имеют средств для описания статических связей. Однако, есть библиотечные расширения (SystemC) над языком C/C++, которые позволяют моделировать системное поведение модели посредством описания интерфейсов, очередей, сигналов в статическом и динамическом виде, но подобное моделирование не учитывает реальные физические процессы в микросхеме.

Верификация разрабатываемых алгоритмов достигается за счет последовательного применения тестовых векторов разработанных на предыдущих стадиях. Тестовый вектор может являться оцифрованной смесью сигнала и шума, бинарной конфигурацией ошибок с заданными свойствами, любым набором тестовых значений, который будучи поданными на вход разрабатываемого устройства или элемента этого устройства вызовут предсказанную (на предыдущей стадии) реакцию. Хотелось бы отметить, что алгоритмы помехоустойчивого кодирования исправляют все ошибки, в том числе ошибки разработчика и программиста, поэтому часть тестов не связанная с моделированием Монте-Карло в белом гауссовском шуме, может быть пройдена успешно и при наличии ошибок в реализации. Полную верификацию обеспечивают статистически достоверное моделирование на ПЛИС по методу Монте Карло в канале, где аддитивной помехой является белый гауссовский шум (БГШ).

Поэтому весьма актуальной является задача разработки компонентов такой модели, в частности генератора белого гауссовского шума в целых числах для реализации его на ПЛИС. Известные алгоритмы такие Бокса-Мюллера [G. E. P. Box and M. E. Muller, “A note on the generation of randomnormal deviates,” Ann. Math. Stat., vol. 29, pp. 610–61, 1958.] и полярный [Marsaglia, G.; Bray, T. A. (1964). "A Convenient Method for Generating Normal Variables". SIAM Review. 6 (3): 260–264. doi:10.1137/1006063. JSTOR 2027592., D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (second edition). Addison-Wesley, Menlo Park, 1981.] требуют вычисления функций log, sin, cos, что является сложной задачей для реализации в целочисленной арифметике. Уоллес предложил свой метод [C. S. Wallace "Fast Pseudorandom Generators for Normal and Exponential Variates", ACM Transactions on Mathematical Software, Vol. 22, No 1, March 1996, Pages 119-127] не требовавший вычислений с плавающей точкой, по крайней мерее на каждом такте.

Способ Уоллеса состоит в следующем:

• заранее заполняют массив из элементов гауссовскими случайными величинами с нулевым матожиданием и единичной дисперсией;

• формируют адресов для доступа к массиву, первый из которых равномерно распределенное случайное число от до , а остальные ;

• для случайных величин выполняют ортогональное линейное преобразование путем умножения на ортогональную матрицу, получая новых отсчетов;

• раз повторяют шаги 2 и 3 формируют новый массив из , перемежают его записывая по строкам и читая по столбцам в перемежителе , перемеженным массивом заменяют первоначально инициализированный массив;

• вычисляют корректирующий множитель использую последний элемент из нового массива, домножают на корректирующий нормирующий множитель на элементов массива, которые являются выходом алгоритма/

В дальнейшем алгоритм для улучшения статистических свойств в частности снижения корреляциями между отсчетами претерпел ряд изменений. Современная реализация модифицированного алгоритма Уоллеса дана в [Dong-U Lee, Wayne Luk, John D. Villasenor, Guanglie Zhang, Philip H. W. Leong "A Hardware Gaussian Noise Generator Using the Wallace Method" IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 13, NO. 8, AUGUST 2005].

Необходимость корректирующего множителя обусловлена тем, что в случае его отсутствия, сумма квадратов каждых отсчетов была бы константой, что неприемлемо для моделирования. В качестве генератора 32-битных равномерных случайных чисел используют генератор Таусворта [P. L’Ecuyer, “Maximally equidistributed combined Tausworthe generators,” Math. Comput., vol. 65, no. 213, pp. 203–213, 1996] с порождающим полиномом . Периодичность такого генератора бит.

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

для матрицы ,

для матрицы .

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

Рассмотрим работу блока формирования адресов. Операция суммы с последующим сложением результата по модулю 2 является быстрой операцией, которая может быть выполнена за один такт. Также быстрой является операция умножение на 2, которая, по сути, является битовым сдвигом или перекомпоновкой бит и не требует временных затрат. Однако операция умножения на 3 занимает целый такт и может быть выполнена как сумма . Таким образом, вычисление займет два такта, а вычисление остальных адресов – один такт, что является недостатком данной схемы, так как ограничивает быстродействие блока.

Аналогом является китайская заявка Gaussian white noise generator based FPGA CN201810037910.5A, CN108390648A приоритет 2018/01/16 опубликована 2018/08/10, где приведен генератор белого гауссовского шума, реализованный по алгоритму Уоллеса [C. S. Wallace, Fast Pseudo-Random Generators for Normal and Exponential Variates, ACM Trans. on Mathematical Software 22 (1996), 119–127]. Способ, реализованный в данном устройстве, отличается от способа из статьи [Dong-U Lee, Wayne Luk, John D. Villasenor, Guanglie Zhang, Philip H. W. Leong "A Hardware Gaussian Noise Generator Using the Wallace Method" IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 13, NO. 8, AUGUST 2005] тем, что

• взят другой генератор равномерных случайных величин (более простой);

• адреса вычисляют по формулам

Вычисление каждого из адресов займет не больше такта, так как в случае суммирование с единицей есть просто присоединение дополнительного бита. Однако в [Dong-U Lee, Wayne Luk, John D. Villasenor, Guanglie Zhang, Philip H. W. Leong "A Hardware Gaussian Noise Generator Using the Wallace Method" IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 13, NO. 8, AUGUST 2005] указывают, что изменение алгоритма генерации адресов весьма критично влияет на статистические свойства результирующей последовательности, поэтому точное выполнение алгоритма Уоллеса в плане генерации псевдослучайных адресов имеет важное значение. В заявке CN108390648A добились сбалансированного вычисления адресов, т.е. каждый адрес вычисляют за одинаковое количество тактов, только за счет изменения оригинального алгоритма.

Задачу упрощения устройства, в частности балансировки вычислений в блоке формирование адреса решает устройство-аналог [Чен Ён Gaussian white noise generator based FPGA CN201810037910.5A, CN108390648A], однако, при этом адреса формируют иным способом, чем в устройстве прототипе, что может вызвать ухудшение статистических свойств результирующей последовательности отсчетов белого гауссовского шума.

Наиболее используемой в настоящее время является двухпортовая память, которая позволяет получить доступ для записи или чтения одновременно к двум адресам. Однако, известны разработки [Kevin R. Townsend, Osama G. Attia, Phillip H. Jones, and Joseph Zambreno "A Scalable Unsegmented Multiport Memory for FPGA-Based Systems", International Journal of Reconfigurable Computing Volume 2015, Article ID 826283, 12 pages], позволяющие организовать эффективный многопортовый доступ к памяти. Таким образом, видно, что эффективность и быстродействие генератора цифрового белого шума может быть значительно повышена за счет балансировки вычислений и применения многопортовой памяти.

Задача, на решение которой направлено заявляемое изобретение – повышение эффективности испытания радиоэлектронной аппаратуры, в частности, системы моделирования помехоустойчивых кодов.

Для решения поставленной задачи в генератор цифрового белого гауссовского шума, содержащий последовательно соединенные генератор равномерных случайных чисел (ГРСЧ) и мультиплексор, три выхода которого соединены с соответствующими входами блока формирования адресов, два выхода которого через блок памяти соединены с соответствующими входами блока ортогонального преобразования, два выхода которого соединены с соответствующими входами блока памяти и блока коррекции, два выхода которого являются выходами устройства, при этом выход блока инициализации соединен с пятым входом блока памяти, кроме того, блок формирования адресов содержит узел сдвига, вход которого соединен с первым входом первого сумматора и является вторым входом блока формирования адресов, соответствующим сигналу ; выход узла сдвига соединен с первым входом второго сумматора, второй вход которого соединен со вторым входом первого сумматора и является первым входом блока формирования адресов, соответствующим сигналу ; вторые входы первого, второго, третьего и четвертого узлов "исключающее или" объединены и являются входом блока формирования адресов, соответствующим сигналу ; выходы узлов "исключающее или" являются выходами блока формирования адресов, соответствующим сигналам , согласно изобретению, в блок формирования адресов введен вычитатель, первый вход которого соединен с входом узла сдвига, второй вход вычитателя объединен с первым входом второго узла "исключающее или" и соединен с первым входом блока формирования адресов, при этом выход вычитателя соединен с первым входом первого узла "исключающее или"; выходы первого и второго сумматоров соединены соответственно с первыми входами третьего и четвертого узлов "исключающее или", кроме того, третий и четвертый выходы блока формирования адресов через блок памяти соединены с соответствующими входами блока ортогонального преобразования, третий и четвертый выходы которого соединены с соответствующими входами блока памяти и блока коррекции, третий и четвертый выходы которого являются соответствующими выходами генератора, причем четвертый выход мультиплексора соединен с пятым входом блока ортогонального преобразования.

Графические материалы, используемые в описании:

Фиг. 1 – схема устройства-прототипа;

Фиг. 2 –схема блока формирователя адреса в устройстве-прототипе;

Фиг. 3– схема заявляемого устройства;

Фиг. 4 – схема блока формирователя адреса в заявляемом устройстве.

Наиболее близким по технической сущности к предлагаемому является устройство, описанное в [Dong-U Lee, Wayne Luk, John D. Villasenor, Guanglie Zhang, Philip H. W. Leong "A Hardware Gaussian Noise Generator Using the Wallace Method" IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 13, NO. 8, AUGUST 2005], принятое за прототип.

На фиг. 1 представлена схема устройства-прототипа, где обозначено:

1 – генератор равномерных случайных чисел (ГРСЧ);

2 – мультиплексор;

3 – блок формирования адресов (БФА);

4 – блок памяти;

5 – блок инициализации;

6 – блок ортогонального преобразования;

7 – блок коррекции.

Устройство-прототип содержит последовательно соединенные генератор равномерных случайных чисел 1 и мультиплексор 2, три выхода которого соединены с соответствующими входами блока формирования адресов 3, выходы которого соединены с соответствующими входами блока памяти 4, первый и второй выходы которого соединены соответственно с входами блока ортогонального преобразования 6, выходы которого соединены с соответствующими входами блока памяти 4 и блока коррекции 7, два выхода которого являются выходами устройства. При этом выход блока инициализации 5 подсоединен к пятому входу блока памяти 4.

На фиг. 2 приведена схема блока формирования адресов устройства-прототипа, где обозначено:

3.1 – узел сдвига;

3.3, 3.4, 3.9, 3.10 – первый, второй, третий и четвертый сумматоры;

3.5, 3.6, 3.7, 3.8 – первый, второй, третий и четвертый узлы "исключающее или".

Блок формирования адресов содержит узел сдвига 1, первый 3.3, второй 3.4, третий 3.9 и четвертый 3.10 сумматоры, а также первый 3.5, второй 3.6, третий 3.7 и четвертый 3.8 узлы "исключающее или". При этом вход узла сдвига 1, первые входы первого 3.3 и второго 3.9 сумматоров объединены и являются вторым входом блока формирования адресов 3 и соответствуют сигналу Выход узла сдвига 1 соединен с объединенными входами первого 3.3 и третьего 3.9 сумматоров. Вторые входы первого 3.3, третьего 3.9 и четвертого 3.10 сумматоров и первый вход первого узла "исключающее или" 3.5 объединены и являются первым входом блока формирования адресов 3, и соответствует сигналу . Выход второго сумматора 3.4 через четвертый сумматор 3.10 соединен с первым входом четвертого узла "исключающее или" 3.8. Выход третьего сумматора 3.9 соединен с первым входом третьего узла "исключающее или" 3.7. Выход первого сумматора 3.3 соединен с первым входом второго узла "исключающее или" 3.6. При этом вторые входы первого 3.5, второго 3.6, третьего 3.7 и четвертого 3.8 узлов "исключающее или" объединены и являются третьим входом блока формирования адресов 3, соответствующий сигналу . Выходы узлов "исключающее или" 3.5, 3.6, 3.7 и 3.8 являются выходами блока формирования адресов 3, соответствующие сигналам .

Работает устройство-прототип следующим образом:

• заранее заполняют массив из элементов гауссовскими случайными величинами с нулевым матожиданием и единичной дисперсией;

• в каждом такте, используя 32-битный отсчет генератора равномерных случайных чисел, формируют 2 10-битных числа: и одно 9-битное путем последовательного взятия бит, с первого по десятый, с одиннадцатого по двадцатый, с двадцать первого по 29;

• в каждый такт формируют 4 адреса:

• считывают по сформированным адресам отсчеты , формируют 4-х мерный вектор , выполняют ортогональное линейное преобразование , где ,

матрицы и используют попеременно и меняют через каждые отсчета;

• полученные отсчеты записывают в массив по новым адресам , полученным за то время, пока выполнялось ортогональное преобразование;

• также отсчеты поступают на вход блока коррекции, где каждый отсчет умножают на корректирующий множитель , получая отсчеты , которые являются выходом алгоритма;

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

На фиг. 3 приведена схема предлагаемого устройства, где обозначено:

1 – генератор равномерных случайных чисел (ГРСЧ);

2 – мультиплексор;

3 – блок формирования адресов (БФА);

4 – блок памяти;

5 – блок инициализации;

6 – блок ортогонального преобразования;

7 – блок коррекции.

Предлагаемое устройство содержит последовательно соединенные генератор равномерных случайных чисел 1 и мультиплексор 2, три выхода которого соединены с соответствующими входами блока формирования адресов 3 и соответствуют сигналам . Выходы блока формирования адресов 3 соединены с соответствующими входами блока памяти 4, четыре выхода которого соединены с соответствующими входами блока ортогонального преобразования 6, выходы которого соединены с соответствующими входами блока памяти 4 и блока коррекции 7, выходы которого являются выходами устройства. Выход блока инициализации 5 соединен с соответствующим входом блока памяти 4. Четвертый выход мультиплексора 2, соответствующий сигналу , подключен к пятому входу блока ортогонального преобразования 6.

На фиг. 4 представлена схема блока формирования адресов, где обозначено:

3.1 – узел сдвига;

3.2 – вычитатель;

3.3, 3.4 – первый и второй сумматоры;

3.5, 3.6, 3.7, 3.8 – первый, второй, третий и четвертый узлы "исключающее или".

Блок формирования адресов 3 содержит узел сдвига 1, вычитатель 3.2, первый 3.3 и второй 3.4 сумматоры, а также первый 3.5, второй 3.6, третий 3.7 и четвертый 3.8 узлы "исключающее или". При этом вход узла сдвига 1, первые входы вычитателя 3.2 и первого сумматора 3.3 объединены и являются вторым входом блока формирования адресов 3 и соответствуют сигналу Выход узла сдвига 1 через второй сумматор 3.4 соединен с первым входом четвертого узла "исключающее или" 3.8. Выход вычитателя 3.2 соединен с первым входом первого узла "исключающее или" 3.5. Выход первого сумматора 3.3 соединен с первым входом третьего узла "исключающее или" 3.7. Первый вход второго узла "исключающее или" 3.6 соединен со вторыми входами вычитателя 3.2, первого 3.3 и второго 3.4 сумматоров и является первым входом блока формирования адресов 3 и соответствует сигналу . Кроме того, вторые входы первого 3.5, второго 3.6, третьего 3.7 и четвертого 3.8 узлов "исключающее или" объединены и являются входом блока формирования адресов 3, соответствующий сигналу . Выходы узлов "исключающее или" являются выходами блока формирования адресов 3, соответствующие сигналам .

Работает заявляемое устройство следующим образом.

В генераторе равномерных случайных чисел (ГРСЧ) 1 формируют 32-разрядное равномерное случайное число из которого в мультиплексоре 2 формируют два 10-разрядных сигнала: и и один 9-разрядный сигнал stride для блока формирования адресов 3, а также однобитный сигнал для блока ортогонального преобразования 6. В блоке формирования адресов 3 параллельно формируют четыре адреса по формуле:

по которым проводят считывание отсчетов для блока ортогонального преобразования 6, а также запись текущих отсчетов с выхода блока ортогонального преобразования 6, в блоке ортогонального преобразования проводят преобразования входных сигналов по формулам:

,

,

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

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

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

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

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