Регистры сдвига с обратными связями

Сентябрь 3, 2022

Главная
Алгебра
Регистры сдвига с обратными связями

Содержание

2. Классификация РЕГИСТРЫ Параллельные Регистры сдвига Специальные Регистры последовательных приближений Универсальные
3. Обратные связи Счетчик Джонсона Упорядоченная последовательность Упорядоченная но очень сложная последовательность. Сложность зависит от длины регистра
4. Реализация обратных связей Конфигурация Фибоначчи Конфигурация Галуа XOR Коэффициент. Если gi=1 – есть соединение и соответствующая
5. Последовательности максимальной длины М-последовательности Maximum length sequence Число состояний набора из M триггеров = 2M Для
6. Последовательности максимальной длины Как сделать М-последовательности Реализация вечности Фибоначчи или Галуа
7. Последовательности максимальной длины Как сделать М-последовательности. Кусок таблицы для конфигурации Галуа Переход от номеров отводов Галуа
8. Псевдослучайная последовательность. PRBS Pseudo Random Binary Sequence Последовательность детерминирована, но никогда не повторится. Период 5,40E+22 лет
9. Защита информации Q=Data Идея Здесь полная мешанина Исходные данные Восстановленные данные Случайная последовательность
10. Защита информации Ключ приемника должен совпадать с ключом приемника. Используется детерминированность ПСП.
11. Проверка целостности информации Контрольная сумма или циклический избыточный код Cyclic Redundancy Code (CRC) ИДЕЯ МЕТОДА Допустим
12. Проверка целостности информации Двоичная информация Любая информация представляет собой набор 0 и 1. 10010001011110001010100100100101010010001111010 В соответствии
13. Контрольная сумма Представление битовых последовательностей полиномами. 1001101011=X9+X6+X5+X3+X1+1
14. Контрольная сумма Полиномиальная арифметика. Арифметика по модулю 2 (без переносов). XOR Суммирование = вычитанию A=X9+X6+X5+X3+X1+1 B=X6+X3+X2+1
15. Контрольная сумма Полиномиальная арифметика. Арифметика по модулю 2 A=X9+X6+X5+X3+X1+1 B=X6+X3+X2+1 Умножение AxB=(X9+X6+X5+X3+X1+1)x(X6+X3+X2+1)= X15+X12+X11+X9+X7+X6+ X12+X9+X8+X6+X4+X3+ X12+X8+X7+X5+X3+X2+ X9+X6+X5+X3+X1+1
16. Контрольная сумма Полиномиальная арифметика. Арифметика по модулю 2 A=X9+X6+X5+X3+X1+1 B=X6+X3+X2+1 Деление Остаток Результат (целая часть) Это
17. Проверка целостности информации Получение остатка с помощью LFSR Такие схемы просто реализуется как на аппаратном уровне,
18. Контрольная сумма Порождающий полином: X4+X1+1 Получение остатка с помощью LFSR. Пример.
19. Контрольная сумма Пример. Кодирование. Порождающий полином: X4+X1+1 Остаток Результат (целая часть). Ненужная
20. Контрольная сумма Пример. Кодирование. Остаток X2 Порождающий полином: X4+X1+1 Старший разряд Младший разряд +1 Разряд X1
21. Контрольная сумма Пример. Кодирование. Порождающий полином: X4+X1+1 Старшим разрядом вперед.
22. CRC Cyclic Redundancy Code
23. Контрольная сумма
25. Скачать презентацию

Слайд 2

Классификация
РЕГИСТРЫ
Параллельные
Регистры сдвига
Специальные
Регистры последовательных приближений
Универсальные

Слайд 3

Обратные связи
Счетчик Джонсона
Упорядоченная последовательность
Упорядоченная но очень сложная последовательность.
Сложность зависит от длины

регистра и расположения обратных связей.

Крутой замес

Слайд 4

Реализация обратных связей
Конфигурация Фибоначчи
Конфигурация Галуа
XOR
Коэффициент.
Если gi=1 – есть соединение и соответствующая

функция XOR
Если gi=0 – нет

Какие обратные связи сделать и зачем?

Начальное состояние всех триггеров не должно быть = 0

Évariste Galois

Слайд 5

Последовательности максимальной длины
М-последовательности
Maximum length sequence
Число состояний набора из M триггеров =

Для нашего случая состояние со всеми нулями недопустимо!

Максимальное число допустимых состояний нашего регистра из M триггеров = 2M -1

Справка:
Возраст Вселенной составляет 13,75E+9 лет

Это ВЕЧНОСТЬ

Слайд 6

Последовательности максимальной длины
Как сделать М-последовательности
Реализация вечности
Фибоначчи
или
Галуа

Слайд 7

Последовательности максимальной длины
Как сделать М-последовательности.
Кусок таблицы для конфигурации Галуа
Переход от

номеров отводов Галуа к Фибоначчи и наоборот:
M-g
(кроме старшего).

[20, 19, 16, 14]

[20, 1, 4, 6]

N- количество триггеров

Схема с 2-мя отводами

Схема с 4-мя отводами

Слайд 8

Псевдослучайная последовательность. PRBS
Pseudo Random Binary Sequence
Последовательность детерминирована, но никогда не

повторится. Период 5,40E+22 лет
При частоте Clk 100 МГц.

Такая последовательность называется псевдослучайной или
ПСП
Pseudo Random Binary Sequence
PRBS

Слайд 9

Защита информации
Q=Data
Идея
Здесь полная мешанина
Исходные данные
Восстановленные данные
Случайная последовательность

Слайд 10

Защита информации
Ключ приемника должен совпадать с ключом приемника.
Используется детерминированность ПСП.

Слайд 11

Проверка целостности информации
Контрольная сумма или циклический избыточный код
Cyclic Redundancy Code

(CRC)

ИДЕЯ МЕТОДА

Допустим надо передать (или сохранить) десятичное число 23567.
Возможно искажение. Как проверить правильность числа?
Поделить исходное число на какую либо постоянную. Допустим на 23. В результате целочисленного деления получим 1024 и остаток 15. Если теперь к исходному числу прибавить 15, то новое число будет делиться на 23 без остатка. Это признак правильности. Но исходное число будет потеряно.
Выход. Число 23567 дополняем нулями. Количество нулей должно совпадать с разрядностью остатка (делителя). Получаем 2356700. Теперь это число делим на 23. Получаем 102465 и остаток 05. Интересует только остаток. Храним или передаем число в форме 2356705.

Исходные данные

Контрольная сумма

При приеме делим 2356705 на наше 23.
Если остаток ≠ 0, то число искажено.
Если остаток = 0, то число с некоторой вероятностью правильное.

Слайд 12

Проверка целостности информации
Двоичная информация
Любая информация представляет собой набор 0 и 1.
10010001011110001010100100100101010010001111010
В

соответствии с идеей надо дописать слово нулями
100100010111100010101001001001010100100011110100000
взять некий делитель, например 1011(с разрядностью по количеству дописанных нулей.
Поделить
Дописать вместо нулей остаток от деления.
10010001011110001010100100100101010010001111010xxxx
Хранить или передавать в такой форме.
Перед использование проверить на делимость без остатка на 1011.

Все по идее просто, но
Делить – это долго и муторно!!!
Даже для этого примера лень было найти реальный остаток и написал xxxx

Нужна другая БЫСТРАЯ арифметика.

Слайд 13

Контрольная сумма
Представление битовых последовательностей полиномами.
1001101011=X9+X6+X5+X3+X1+1

Слайд 14

Контрольная сумма
Полиномиальная арифметика.
Арифметика по модулю 2 (без переносов).

XOR

Суммирование = вычитанию
A=X9+X6+X5+X3+X1+1
B=X6+X3+X2+1
A+B=A-B=B-A= X9+X6+X5+X3+X1+1+

X6+X3+X2+1= X9+X5+X2+X1

Переноса нет!

Слайд 15

Контрольная сумма
Полиномиальная арифметика.
Арифметика по модулю 2
A=X9+X6+X5+X3+X1+1
B=X6+X3+X2+1
Умножение
AxB=(X9+X6+X5+X3+X1+1)x(X6+X3+X2+1)=
X15+X12+X11+X9+X7+X6+ X12+X9+X8+X6+X4+X3+ X12+X8+X7+X5+X3+X2+ X9+X6+X5+X3+X1+1 =
X15+X12+X11+X9+X6+X4+X3+X2+X1+1

Слайд 16

Контрольная сумма
Полиномиальная арифметика.
Арифметика по модулю 2
A=X9+X6+X5+X3+X1+1
B=X6+X3+X2+1
Деление
Остаток
Результат (целая часть)
Это гораздо проще чем

обычное деление.

Разрядная сетка

Умножили

Отняли

Умножили

Отняли

Слайд 17

Проверка целостности информации
Получение остатка с помощью LFSR
Такие схемы просто реализуется как

на аппаратном уровне, так и на программном.
Количество триггеров соответствует полиному – делителю.
Делитель называется порождающим полиномом.

LFSR со входом

1001000101111000101010010010010101001000111101000..0

N разрядное входной полином

Дописанное M нулями поле для CRC

Все слово подается поразрядно на вход LFSR. Старшим разрядом вперед.

За N+M тактов в триггерах останется остаток от деления по модулю 2.

Слайд 18

Контрольная сумма
Порождающий полином: X4+X1+1
Получение остатка с помощью LFSR. Пример.

Слайд 19

Контрольная сумма
Пример. Кодирование.
Порождающий полином: X4+X1+1
Остаток
Результат (целая часть).
Ненужная

Слайд 20

Контрольная сумма
Пример. Кодирование.
Остаток X2
Порождающий полином: X4+X1+1
Старший разряд
Младший разряд +1
Разряд X1
Разряд X2

Слайд 21

Контрольная сумма
Пример. Кодирование.
Порождающий полином: X4+X1+1
Старшим разрядом вперед.

Слайд 22

CRC
Cyclic Redundancy Code

Слайд 23

Регистры сдвига с обратными связями

Содержание

КлассификацияРЕГИСТРЫПараллельныеРегистры сдвигаСпециальныеРегистры последовательных приближенийУниверсальные

Обратные связиСчетчик ДжонсонаУпорядоченная последовательностьУпорядоченная но очень сложная последовательность.Сложность зависит от длины

Реализация обратных связейКонфигурация ФибоначчиКонфигурация ГалуаXORКоэффициент.Если gi=1 – есть соединение и соответствующая

Последовательности максимальной длиныМ-последовательностиMaximum length sequenceЧисло состояний набора из M триггеров =

Последовательности максимальной длиныКак сделать М-последовательностиРеализация вечностиФибоначчиилиГалуа

Последовательности максимальной длиныКак сделать М-последовательности. Кусок таблицы для конфигурации ГалуаПереход от

Псевдослучайная последовательность. PRBS Pseudo Random Binary SequenceПоследовательность детерминирована, но никогда не

Защита информацииQ=DataИдеяЗдесь полная мешанинаИсходные данныеВосстановленные данныеСлучайная последовательность

Защита информацииКлюч приемника должен совпадать с ключом приемника.Используется детерминированность ПСП.

Проверка целостности информацииКонтрольная сумма или циклический избыточный код Cyclic Redundancy Code

Проверка целостности информацииДвоичная информацияЛюбая информация представляет собой набор 0 и 1. 10010001011110001010100100100101010010001111010В

Контрольная суммаПредставление битовых последовательностей полиномами.1001101011=X9+X6+X5+X3+X1+1

Контрольная суммаПолиномиальная арифметика.Арифметика по модулю 2 (без переносов). XOR Суммирование = вычитаниюA=X9+X6+X5+X3+X1+1B=X6+X3+X2+1A+B=A-B=B-A= X9+X6+X5+X3+X1+1+

Контрольная суммаПолиномиальная арифметика.Арифметика по модулю 2A=X9+X6+X5+X3+X1+1B=X6+X3+X2+1ДелениеОстатокРезультат (целая часть)Это гораздо проще чем

Проверка целостности информацииПолучение остатка с помощью LFSRТакие схемы просто реализуется как

Контрольная суммаПорождающий полином: X4+X1+1Получение остатка с помощью LFSR. Пример.

Контрольная суммаПример. Кодирование.Порождающий полином: X4+X1+1ОстатокРезультат (целая часть).Ненужная

Контрольная суммаПример. Кодирование.Остаток X2Порождающий полином: X4+X1+1Старший разрядМладший разряд +1Разряд X1Разряд X2

Контрольная суммаПример. Кодирование.Порождающий полином: X4+X1+1Старшим разрядом вперед.

CRCCyclic Redundancy Code