Разделы презентаций


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

Содержание

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

Слайды и текст этой презентации

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


Linear Feedback Shift Registers
LFSR
20

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

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

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

Слайд 3Обратные связи

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

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

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

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

соответствующая функция XOR
Если gi=0 – нет
Какие обратные связи сделать и

зачем?

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

Évariste Galois

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

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

= 2M
Для нашего случая состояние со всеми нулями недопустимо!
Максимальное

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

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

Это ВЕЧНОСТЬ

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

Слайд 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

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

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

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

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

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

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

Code (CRC)
ИДЕЯ МЕТОДА
Допустим надо передать (или сохранить) десятичное число 23567.


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

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

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

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

Проверка целостности информацииКонтрольная сумма или циклический избыточный код Cyclic Redundancy Code (CRC)ИДЕЯ МЕТОДАДопустим надо передать (или сохранить)

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

1.
10010001011110001010100100100101010010001111010
В соответствии с идеей надо дописать слово нулями
100100010111100010101001001001010100100011110100000
взять некий

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

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

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

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

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

Контрольная суммаПредставление битовых последовательностей полиномами.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
Переноса нет!

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

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

чем обычное деление.
Разрядная сетка
Умножили
Отняли
Умножили
Отняли

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

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

как на аппаратном уровне, так и на программном.
Количество триггеров соответствует

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

LFSR со входом

1001000101111000101010010010010101001000111101000..0

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

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

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


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

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

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

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

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

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

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

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

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


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

Слайд 22CRC

Cyclic Redundancy Code

CRCCyclic Redundancy Code

Слайд 23Контрольная сумма

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

Слайд 24Содержание
Обратные связи
Конфигурация Фибоначчи
Конфигурация Галуа
М-последовательности
Переход от номеров отводов Галуа к Фибоначчи

и наоборот
Pseudo Random Binary Sequence
Защита информации
Ключ приемника должен совпадать с

ключом приемника
Контрольная сумма или циклический избыточный код
Идея метода
Представление битовых последовательностей полиномами
Полиномиальная арифметика -арифметика по модулю 2 (без переносов)
Сложение = вычитание
Умножение
Деление
Получение остатка с помощью LFSR
Получение остатка с помощью LFSR. Пример.
Примеры CRC. E1, RFID, SD, 1-Wire, Bluetooth, Ethernet, Wi-Fi …
СодержаниеОбратные связиКонфигурация ФибоначчиКонфигурация ГалуаМ-последовательностиПереход от номеров отводов Галуа к Фибоначчи и наоборотPseudo Random Binary SequenceЗащита информацииКлюч приемника

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика