Последовательности Де-Брейна и их представление.

В разделе 3 данного отчета были рассмотрены последовательности Де-Брейна, а также, в качестве визуального примера- Граф Де-брейна.Вопрос о реализации последовательности Де-Брейна имеет известное решение – использование линейных регистров сдвига с обратной связью (ЛРСОС).

В общем случае линейные регистры сдвига будут выглядеть следующим образом:

Рисунок 8. Общий вид ЛРС

Изменение функций обратной связи позволяет создавать многочисленные варианты ГПСЧ. Остановимся на конкретном виде функции обратной связи, которые более интересны для нас.

Рисунок 9. ЛРС, Тип 1

bn	…	b2	b1
			xor

А также, еще один вариант для сравнения по сложности:
Рисунок 10. ЛРС, Тип 2

bn-1	bn	…	b2	b1
xor		xor
		xor

 

Написаниепрограммы

 

Алгоритмы реализованы при использовании языка описания аппаратуры VHDL. Ниже приведено блочное представление программных кодов, позволяющих реализовать данные генераторы на ПЛИС, в частности, на программируемых микросхемах семейства XilinxSpartan 3A при использовании специализированной САПР ISE 10.1.

Пример программы для ЛРС типа 1 (Рис. 9) с N=4.

 

library IEEE;

use IEEE.STD_LOGIC_1164.ALL;

 

-- Uncomment the following library declaration if using

-- arithmetic functions with Signed or Unsigned values

--use IEEE.NUMERIC_STD.ALL;

 

-- Uncomment the following library declaration if instantiating

-- any Xilinx primitives in this code.

--library UNISIM;

--use UNISIM.VComponents.all;

 

entity unit is

Port ( c : in STD_LOGIC;

q : out STD_LOGIC_VECTOR (3 downto 0));

end unit;

 

architecture Behavioral of unit is

 

signal t : std_logic_vector (3 downto 0) := "0101";

 

begin

 

t <= t(2 downto 0) & (t(3) xor t(0)) when rising_edge(c);

q<= t;

 

endBehavioral;

 

Пример программы для ЛРС типа 2 (Рис. 10) с N=4.

library IEEE;

use IEEE.STD_LOGIC_1164.ALL;

 

-- Uncomment the following library declaration if using

-- arithmetic functions with Signed or Unsigned values

--use IEEE.NUMERIC_STD.ALL;

 

-- Uncomment the following library declaration if instantiating

-- any Xilinx primitives in this code.

--library UNISIM;

--use UNISIM.VComponents.all;

 

entity unit is

Port ( c : in STD_LOGIC;

q : out STD_LOGIC_VECTOR (3 downto 0));

end unit;

 

architecture Behavioral of unit is

 

signal t : std_logic_vector (3 downto 0) := "0101";

 

begin

t <= t(2 downto 0) & ((t(1) xor t(0)) xor (t(3) xor t(2))) when rising_edge(c);

q<= t;

 

endBehavioral;

 

6. Анализ сложности ГПСЧ в базисе ПЛИС

Оценки временной и емкостной сложности реализации ГПСЧ на базе одного устройства ПЛИС семейства Xilinx, получены на основе протоколов работы специализированной САПР Xilinx® ISEDesignSuite 13.2

Вид отчета для ЛРС тип1 (Рис. 9) приведен ниже.

unit Project Status (03/21/2012 - 10:14:48)
Project File:	file_test.xise	Parser Errors:	No Errors
Module Name:	unit	Implementation State:	Synthesized
Target Device:	xc3s700a-4fg484	· Errors:	No Errors
Product Version:	ISE 13.2	· Warnings:	No Warnings
Design Goal:	Balanced	· Routing Results:
Design Strategy:	Xilinx Default (unlocked)	· Timing Constraints:
Environment:	System Settings	· Final Timing Score:

 

Device Utilization Summary (estimated values)	[-]
Logic Utilization	Used	Available	Utilization
Number of Slices			0%
Number of Slice Flip Flops			0%
Number of 4 input LUTs			0%
Number of bonded IOBs			1%
Number of GCLKs			4%

 

Рисунок 11. Протокол работы САПР при ЛРС тип 1, N=4

 

 

Для выявления максимально возможного количества разрядов ЛРС тип 1 (Рис. 9), изменим программу, увеличив размер вектора:

39 signal t :std_logic_vector (3 downto 0) := "0101";

39 signal t :std_logic_vector (7 downto 0) := "0101010101";

 

а также, функцию обратной связи:

43 t <= t(2 downto 0) & (t(3) xor t(0)) when rising_edge(c);

43 t <= t(6downto 0) & (t(7) xor t(0)) when rising_edge(c);

 

После произведения изменений, производим синтез проекта в САПР Xilinx® ISEDesignSuite 13.2.
По завершению синтеза, нам будут доступны обновленные данные из протокола САПР. Составим таблицу из данных протокола.

 

Рисунок 12. Данные о сложности полученного ГПСЧ с увеличением числаразрядов регистра сдвига.

 

Как видно из рисунка 12, при увеличении разрядов ГПСЧ, сложность возрастает линейно. Также, следует обратить внимание на число разрядов равное 372. Данное число разрядов для конкретной ПЛИС и конкретного типа ЛРС (Рис. 9) является максимальным. Это происходит по причине того, что задействовано максимальное количество доступных блоков ввода-вывода в ПЛИС.

Так как дальше мы пойдем по пути усложнения ЛРС и функции обратной связи, а вид ЛРС является наипростейшим, мы можем на данном этапе определить максимально возможное количество разрядов для нашего ГПСЧ. Оно равно 372.

Теоретически, можно построить РЛС N-разрядов, и протоколы САПР выдадут адекватный результат, но запрограммировать ГПСЧ с числом разрядов, превышающим 372, не представляется возможным (на данном типе ПЛИС, конечно).

 

Для сравнения по сложности, приведем таблицу и график для ЛРС 2 типа (Рис. 10) с N=32.

Device Utilization	number of bits
Number of Slices
Number of Slice Flip Flops
Number of 4 input LUTs
Number of bonded IOBs
Number of GCLKs

 

Рисунок 13. Данные о сложности полученного ГПСЧ с увеличением числа разрядов регистра сдвига до 32.

 

Данный график также показывает линейность возрастания сложности ГПСЧ с ЛРС 2 типа. Стоит отметить, что в данном случае задействуется большее число LUT'ов, что логично, ибо количество сумматоров возросло. Следовательно, мы определяем еще6 один предел сложность количествоLUT'ов, максимальное число которых равно 11776.

 

7. Цели на дипломный проект

В пункте 5 данного очета была представлена реализация линейного регистра сдвига с простой функцией обратной связи. Данная конфигурация позволяет получать числовые последовательности с хорошими статистическими свойствами. Но, несмотря на хорошие показатенли, данные последовательности легко предсказуемы. Достаточно собрать 93 последовательности, сгенерированные подобным линейным ГПСЧ, чтобы расшифровать функцию обратной связи. Посему, использование данного вида ГПСЧ в целях криптографии весьма ненадежно.

Нашей задачей на дипломный проект будет добавление нелинейности к функции обратной связи. Примертакойнелинейностиизображеннарис. 14.

Рисунок 14. Пример добавление нелинейности в ЛРС.

 

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

Также, необходимо реализовать данный вид ЛРС в базисе ПЛИС и проанализировать характеристики сложности и быстродействию полученного ГПСЧ.

 

Заключение

В процессе прохождения преддипломной практики было изучено множество теоретического материала по последовательностям Де-Брейна и их возможной реализации. Также были изучены различные алгоритмы генераторов псевдослучайных чисел, что позволило сделать качественную оценку генератора, который мне необходимо реализовать.

 

Также была изучена работа на ПЛИС, в частности, на программируемых микросхемах семейства Xilinx серии Spartan3A при использовании специализированной САПР ISE 13.2. Также, изучены протоколы синтеза САПР, для определения временных и аппаратных характеристик полученного генератора.

 

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

 

Литература

 

1. Холл М. Комбинаторика: Пер. с англ. М.:Мир, 1970. 424 с.

2. Свердлик М.Б.Оптимальные дискретные сигналы: 1975. 100с.

3. http://math.nsc.ru/LBRT/k3/Graph/Bruijn.html

4. http://ru.wikipedia.org/wiki/Последовательность_де_Брейна

5. http://habrahabr.ru/hub/controllers/posts/

6. http://chipnews.gaw.ru/html.cgi/arhiv/02_01/6.htm

7. http://kit-e.ru/articles/plis/2005_3_130.php

8. http://www.plis.ru/page.php?id=12