Линейная обратная связь сдвиг регистр?
https://stackoverflow.com/questions/3735217
-
03-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В последнее время я неоднократно столкнулся с концепцией LFSR, что я нахожу довольно интересным из-за его связей с разными полями, а также очаровывающимся сам по себе. Мне потребовалось несколько усилий, чтобы понять, окончательная помощь была это действительно хорошо страница, намного лучше, чем (сначала) загадочный Вход в Википедии. Отказ Поэтому я хотел написать небольшой код для программы, которая работала как LFSR. Быть более точным, что как-то показало, как работает LFSR. Вот самая чистая вещь, с которой я мог бы придумать после некоторых жизненных попыток (Python):
def lfsr(seed, taps):
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
sr, xor = str(xor) + sr[:-1], 0
print sr
if sr == seed:
break
lfsr('11001001', (8,7,6,1)) #example
Я назвал «XOR» вывод функции XOR, не очень правильный. Тем не менее, это просто предназначено для того, чтобы показать, как это круги через возможные состояния, на самом деле вы заметили, что реестр представлен строкой. Не очень логическая согласованность.
Этого можно легко превратить в хорошую игрушку, которую вы можете посмотреть часами (по крайней мере, я мог бы :-)
def lfsr(seed, taps):
import time
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
print
time.sleep(0.75)
sr, xor = str(xor) + sr[:-1], 0
print sr
print
time.sleep(0.75)
Тогда это ударило меня, что это использование в написании программного обеспечения? Я слышал, что он может генерировать случайные числа; это правда? как? Итак, было бы здорово, если бы кто-то мог:
- Объясните, как использовать такое устройство в разработке программного обеспечения
- придумайте какой-нибудь код, чтобы поддержать точку выше или просто как мой, чтобы показать различные способы сделать это, на любом языке
Кроме того, как не очень много дидактических вещей вокруг этого куска логики и цифровой схемы, было бы неплохо, если бы это могло быть место для новичков (например, я), чтобы получить лучшее понимание этого предмет, или лучше, чтобы понять, что это такое и как это может быть полезно при написании программного обеспечения. Должен был сделать это сообществом вики?
Это сказано, если кто-то чувствует себя в гольф ... пожалуйста.
Решение
На самом деле, алгоритмы на основе LFSR очень распространены. CRC на самом деле напрямую основывается на LFSR. Конечно, в компьютерных науках люди говорят о многочленах, когда они говорят о том, как предполагается, что входное значение должно быть ксущевым с накопленным значением, в Electornics Engineering мы говорим о кранах. Они одинаковы только разные терминологии.
CRC32 очень распространенный. Он используется для обнаружения ошибок в рамах Ethernet. Это означает, что когда я опубликовал этот ответ, мой компьютер использовал алгоритм на основе LFSR для генерации хэша IP-пакета, чтобы мой роутер мог убедиться, что то, что он передает, не поврежден.
ZIP и GZIP-файлы являются еще одним примером. Оба используют CRC для обнаружения ошибок. ZIP использует CRC32 и GZIP использует как CRC16, так и CRC32.
CRCS в основном хеш-функции. И это достаточно хорошо, чтобы сделать интернет-работа. Что означает LFSRS довольно хорошие хэш-функции. Я не уверен, что знаете ли вы это, но в целом хорошие хеш-функции считаются хорошими генераторами случайных чисел. Но вещь с LFSR состоит в том, что выбрать правильные краны (полиномы) очень важно для качества хеша / случайного числа.
Ваш код, как правило, Toy Code, поскольку он работает по строке и нулям. В реальном мире LFSR работают на битах в байте. Каждый байт вы нажимаете через LFSR, меняет накопленное значение реестра. Это значение эффективно эффективно контрольная сумма всех байтов, которые вы продвигаете реестр. Два распространенных способа использования этого значения в качестве случайного числа - либо использовать счетчик и толкать последовательность чисел через регистр, тем самым преобразуя линейную последовательность 1,2,3,4 к некоторой хэш-последовательности, как 15306,22,5587, 994 или для передачи текущего значения в реестре, чтобы создать новый номер в кажущейся случайной последовательности.
Следует отметить, что делает это наивно, используя Bit-Diddling LFSR, довольно медленно, поскольку вы должны обработать биты одновременно. Таким образом, люди придумали способами использования предварительно рассчитанных таблиц, чтобы сделать это восемь битов за раз или даже 32 бита за раз. Вот почему вы почти никогда не видите код LFSR в дикой природе. В большинстве производственных кодекса это маскарады как что-то еще.
Но иногда простой бит-Twiddling LFSR может пригодиться. Я однажды написал Модбус Драйвер для фото Micro и этот протокол использовал CRC16. Предварительно рассчитанная таблица требует 256 байтов памяти, и мой процессор имел только 68 байт (я не шучу). Поэтому мне пришлось использовать LFSR.
Другие советы
Так как я искал LFSR-реализацию в Python, я наткнулся на эту тему. Однако я нашел, что следующее было немного более точным в соответствии с моими потребностями:
def lfsr(seed, mask):
result = seed
nbits = mask.bit_length()-1
while True:
result = (result << 1)
xor = result >> nbits
if xor != 0:
result ^= mask
yield xor, result
Вышеуказанный LFSR-генератор основан на GF (2k.) модуль исчисления (GF = Galois Field.). Продовно закончив курс алгебры, я собираюсь объяснить это математическим путем.
Давайте начнем с применения, например, GF (24), который равен {а4Икс4 + А.3Икс3 + А.2Икс2 + А.1Икс1 + А.0Икс0 |. а.0, А.1, ...,4 ∈ Z.2} (уточнить, zN. = {0,1, ..., n-1} и, следовательно, z2 = {0,1}, то есть один бит). Это означает, что это набор всех полиномов четвертой степени со всеми факторами, либо присутствующими, либо нет, но не имеющих нескольких таких факторов (например, нет 2xk.). Икс3, Икс4 + X.3, 1 и х4 + X.3 + X.2 + x + 1 - все примеры членов этой группы.
Мы принимаем этот набор модуля полиномом четвертой степени (т.е. p (x) ∈ GF (24)), например p (x) = x4+ X.1+ X.0. Отказ Эта работа модуля на группе также обозначается как GF (24) / P (x). Для справки P (X) описывает «краны» внутри LFSR.
Мы также принимаем случайный полиномиальный уровень степени 3 или ниже (так, что наш модуль не влияет, иначе мы могли просто выполнить операцию модуля прямо на нем), например,0(х) = х0. Отказ Теперь каждый последующийя(x) рассчитывается путем умножения его с помощью X: Aя(х) = аI-1.(x) * x мод p (x).
Поскольку мы находимся в ограниченном поле, операция модуля может иметь эффект, но только при получениия(х) имеет хотя бы фактор х4 (наш самый высокий фактор в p (x)). Обратите внимание, что, поскольку мы работаем с цифрами в Z2, выполнение самой эксплуатации модуля - не что иное, как определение того,я становится 0 или 1, добавив два значения из p (x) ия(x) вместе (т. Е. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 или «xoring» эти два).
Каждый полиномиал может быть написан как набор битов, например x4+ X.1+ X.0 ~ 10011.0(x) можно рассматривать как семена. Операция «Times X» можно рассматривать как сдвиг левой работы. Операция модуля можно рассматривать как немного маскирующей операции, а маска наша p (x).
Следовательно, алгоритм, изображенный выше, например, генерирует (бесконечный поток) действительных четырех битных моделей LFSR. Например, для нашего определенного0(Икс) (Икс0) и p (x) (Икс4+ X.1+ X.0), Мы можем определить следующие впервые приведенные результаты в GF (24) (Обратите внимание, что0 не дает до конца первого раунда - математики, как правило, начинают рассчитывать на «1»):
i Ai(x) 'x⁴' bit pattern
0 0x³ + 0x² + 0x¹ + 1x⁰ 0 0001 (not yielded)
1 0x³ + 0x² + 1x¹ + 0x⁰ 0 0010
2 0x³ + 1x² + 0x¹ + 0x⁰ 0 0100
3 1x³ + 0x² + 0x¹ + 0x⁰ 0 1000
4 0x³ + 0x² + 1x¹ + 1x⁰ 1 0011 (first time we 'overflow')
5 0x³ + 1x² + 1x¹ + 0x⁰ 0 0110
6 1x³ + 1x² + 0x¹ + 0x⁰ 0 1100
7 1x³ + 0x² + 1x¹ + 1x⁰ 1 1011
8 0x³ + 1x² + 0x¹ + 1x⁰ 1 0101
9 1x³ + 0x² + 1x¹ + 0x⁰ 0 1010
10 0x³ + 1x² + 1x¹ + 1x⁰ 1 0111
11 1x³ + 1x² + 1x¹ + 0x⁰ 0 1110
12 1x³ + 1x² + 1x¹ + 1x⁰ 1 1111
13 1x³ + 1x² + 0x¹ + 1x⁰ 1 1101
14 1x³ + 0x² + 0x¹ + 1x⁰ 1 1001
15 0x³ + 0x² + 0x¹ + 1x⁰ 1 0001 (same as i=0)
Обратите внимание, что ваша маска должна содержать «1» на четвертом положении, чтобы убедиться, что ваш LFSR генерирует четырехбитные результаты. Также обратите внимание, что в положении Zeroth необходимо присутствовать в положении Zeroth, чтобы убедиться, что ваш битовый поток не будет в конечном итоге с шаблоном 0000 битов или что конечный бит станет неиспользованным (если все биты смещены влево, вы бы Также в конечном итоге с нулем в 0-й позиции после одной смены).
Не все P (x) обязательно являются генераторами для GF (2k.) (т.е. не все маски k битов генерируют все 2к-1-1 номера). Например, х4 + X.3 + X.2 + X.1 + X.0 генерирует 3 группы из 5 различных многономалов каждый или «3 цикла периода 5»: 0001,0010,01001000,1111; 0011,0110,1100,0111,1110; и 0101,1010,1011,1001,1101. Обратите внимание, что 0000 никогда не может быть сгенерирован и не может генерировать какой-либо другой номер.
Обычно вывод LFSR - это бит, который «смещен», который является «1», если выполняется операция модуля, и «0», когда это не так. LFSR с периодом 2к-1-1, также называемый псевдо-шум или PN-LFSR, придерживается постулатов случайности Голамба, что говорит так же, как этот выпускной бит является случайной «достаточно».
Следовательно, последовательности этих битов имеют их использование в криптографии, например, в стандартах мобильных шифров A5 / 1 и A5 / 2 или стандартом E0 Bluetooth. Тем не менее, они не такие безопасные, как хотелось бы: Алгоритм Berlekamp-Massey Может использоваться для реверсирующего инженера характерный полиномал (P (X)) LFSR. Поэтому используйте прочные стандарты шифрования Нелинейный FSRили подобные нелинейные функции. Связанная тема к этому S-ящики используется в AES.
Обратите внимание, что я использовал int.bit_length() эксплуатация. Отказ Это не было реализовано до Python 2.7.
Если вам нравится только конечный битовый шаблон, вы можете проверить, равняется ли семя, а затем сломает свой цикл.
Вы можете использовать мой метод LFSR в For-Loop (например, for xor, pattern in lfsr(0b001,0b10011)) или вы можете многократно звонить .next() операция на результате метода, возвращение нового (xor, result)-Пороть каждый раз.
Есть много приложений LFSRS. Один из них генерирует шум, например, SN76489 и варианты (используемые на главной системе, Game Gear, MegAdrive, Neogeo Pocket, ...) Используйте LFSR для генерации белого / периодического шума. Есть действительно хорошее описание LFSR SN76489 На этой странице.
Чтобы сделать это действительно элегантным и пифитонным, попробуйте создать генератор, yield- последовательные ценности от LFSR. Также, сравнивая с плавающей точкой 0.0 не нужно и запутанно.
LFSR - это только один из многих способов создания псевдослучайных чисел на компьютерах. Псевдо-случайно, потому что там нет В самом деле Случайно - вы можете легко повторить их, начиная с семян (начальное значение) и продолжается теми же математические операции.
Ниже приведена вариация вашего кода, используя целые числа и двоичные операторы вместо строк. Он также использует доходность, как кто-то предложен.
def lfsr2(seed, taps):
sr = seed
nbits = 8
while 1:
xor = 1
for t in taps:
if (sr & (1<<(t-1))) != 0:
xor ^= 1
sr = (xor << nbits-1) + (sr >> 1)
yield xor, sr
if sr == seed:
break
nbits = 8
for xor, sr in lfsr2(0b11001001, (8,7,6,1)):
print xor, bin(2**nbits+sr)[3:]
Если мы предположим, что семена представляет собой список INTS, а не строки (или преобразовать его, если это не так), то следующее должно делать то, что вы хотите с немного более элегантностью:
def lfsr(seed, taps) :
while True:
nxt = sum([ seed[x] for x in taps]) % 2
yield nxt
seed = ([nxt] + seed)[:max(taps)+1]
Пример :
for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) :
print x
list_init=[1,0,1,1]
list_coeff=[1,1,0,0]
out=[]
for i in range(15):
list_init.append(sum([list_init[i]*list_coeff[i] for i in range(len(list_init))])%2)
out.append(list_init.pop(0))
print(out)
#https://www.rocq.inria.fr/secret/Anne.Canteaut/encyclopedia.pdf
