- •1.Регистры
- •2. Счетчики
- •2.1 Классификация счетчиков
- •Двоичные счетчики
- •Последовательные (асинхронные счетчики)
- •2.3. Параллельные счетчики
- •2.4.Синтез двоичного реверсивного счетчика
- •2.5. Счетчик с асинхронной загрузкой параллельного кода
- •Описание 8-битного реверсивного счетчика на Verilog
- •Построение счетчика с заданным модулем счета
- •Описание счетчика на Verilog
- •Описание счетчика с модулем счета 5 на Verilog
- •3. Сдвигающие регистры
- •3.4.Сдвигающие регистры, реализованные в виде ис средней степени интеграции
- •Режимы работы сдвигающего регистра определяются комбинацией значений на управляющих входах микросхемы s1, s0. (Таб. 11 )
- •3.5.Устройство быстрого сдвига
- •4. Счетчики на сдвигающих регистраx
- •4.1 Кольцевые счетчики (Ring Counters)
- •4.2. Счетчик Джонсона
- •Полиномиальные счетчики
- •4.3.1. Некоторые определения и понятия из высшей алгебры
- •4.4. Генератор элементов поля Галуа (Galois lfsr)
- •4.8. Сравнение lfsr
- •1.Описание lfsr Галуа на Verilog
- •2. Описание lfsr Fibonacci на Verilog
- •4.9. Загрузка начального состояния в lfsr
4.4. Генератор элементов поля Галуа (Galois lfsr)
Генератор поля Галуа с примитивным многочленом степени n в цепи обратной связи является счетчиком , имеющим pn-1 состояний (если p=2, то 2n-1) .
На рис.39 приведена схема счетчика с числом состояний 25-1.
Рис. 39.
Примитивным многочленом и делителем многочлена x31-1 является многочлен
d(x) = 1+x2+x5, включенный в цепь обратной связи.
Единице, сдвигаемой из старшего разряда, соответствует элемент 5. Обратная связь заменяет его на равный ему элемент 1+2.
Это следует из того, что является корнем d(x) , т.е. 1+ 2 + 5 =0. Отсюда следует, что 5 = 1+2.
Каждому внутреннему многочлену ЛПМ ставится в соответствие вектор (q0,q1, . . . qn-1), где q0,q1, . . . qn-1 - коэффициенты при соответствующих степенях (qi – выход i-й задержки).
Тогда последовательность состояний счетчика будет следующей:
(q0 q1 q2 q3 q4)
S0 0 = 1 1 0 0 0 0
S1 1 = 0 1 0 0 0
S2 2 = 2 0 0 1 0 0
S3 3 = 3 0 0 0 1 0
S4 4 = 4 0 0 0 0 1
S5 5 = 1 + 2 1 0 1 0 0
S6 6 = + 3 0 1 0 1 0
S7 7 = 2 + 4 0 0 1 0 1
S8 8 = 1 + 2 + 3 1 0 1 1 0
.
.
.
S30 30 = + 4 0 1 0 0 1
31 = 0 =1.
LFSR-счетчик никогда не проходит в цикле через состояние 0000. Это состояние является состоянием покоя.
Достоинством полиномиальных счетчиков является то, что сложность комбинационной схемы не зависит от числа разрядов счетчика, а определяется выражением для многочлена, включенного в цепь обратной связи. В случае параллельного двоичного счетчика функция возбуждения старшего разряда зависит от n-1 переменных состояния. Например, для построения счетчика с числом разрядов n=10 и примитивным многочленом в цепи обратной связи 1+x7+x10 требуется всего oдин двухвходовой элемент XOR.
Недостатком, по сравнению с двоичными счетчиками, является то, что необходима перекодировка содержимого счетчика в двоичный код.
Рассмотренные схемы полиномиальных счетчиков называют сдвигающими регистрами с линейной обратной связью (LFSR – linear feedback shift-register), которые используются, в основном, в качестве генераторов псевдослучайных чисел и в ряде других случаев.
Линейным сдвигающим регистром является регистр, который построен только на D-триггерах и схемах “исключающее ИЛИ (сумма по mod 2)”. Функции возбуждения всех триггеров линейны.
4.5. Фибоначчи LFSR (Fibonacci LFSR (n=5))
Другой разновидностью LFSR является Фибоначи LFSR (рис.40).
Рис.40
d(x) = 1+x2+x 5
Последовательность состояний, генерируемых данной схемой, отличается от последовательности состояний LFSR Галуа.
Некоторые полиномы, принадлежащие максимальному показателю
Таб.16
N |
Feedback polynomial |
Period (2n -1) |
2 |
x2 + x +1 |
3 |
3 |
x3 + x +1, x3 + x2 +1 |
7 |
4 |
x4 + x3 +1, x4 + x +1 |
15 |
5 |
x5 + x3 +1, x5 + x2 +1 |
31 |
6 |
x6 + x5 +1, x6 + x +1 |
63 |
8 |
x8+ x6 + x5 +x4 + 1 |
255 |
9 |
x9 + x5 +1, x9 + x4 +1 |
511 |
10 |
x10 + x7 +1 |
1023 |
11 |
x11 + x9 +1, x11 + x2 +1 |
2047 |
12 |
x12+ x11 + x10 +x4 + 1 |
4095 |
13 |
x13+ x12 + x11 +x8 + 1 |
8191 |
П
римеры
3-разрядных LFSR с
полиномом d(x)
= 1 + x2
+ x3
Galois LFSR Рис. 41
Полином d(x) = 1 + x2 + x3 принадлежит максимальному показателю М=23 – 1 .
Схема генерирует все 7 полиномов по модулю неприводимого полинома d(x) = 1 + x2 + x3.
Поэтому данная схема имеет 7 состояний. Эти состояния указаны в таблице 16.
D() =0. 1+2 + 3 =0; 3 = 1+2
Taб.16
-
State
Polynomials
q0 q1 q2
S0
0
1
1 0 0
S1
1
0 1 0
S2
2
2
0 0 1
S3
3
1 + 2
1 0 1
S4
4
1 + + 2
1 1 1
S5
5
1 +
1 1 0
S7
6
+ 2
0 1 1
S8 =S0
7
1
1 0 0
F
ibonacci
LFSR
Рис.42
Последовательность состояний счетчика представлена в Таб. 17.
Таб.17
-
State
q2 q1 q0
S0
1 0 0
S1
1 1 0
S2
1 1 1
S3
0 1 1
S4
1 0 1
S5
0 1 0
S7
0 0 1
S8 =S0
1 0 0
П
оследовательность
состояний отличается от последовательности
состояний генератора элементов поля
Галуа.
4.7. Примеры 8-миразрядных LFSR с d(x) =1+ x4 + x5 + x6 + x8
1
.
Galois
LFSR
Рис. 43
2
.
Fibonacci
LFSR Рис.
44
