Регистр сдвига с обобщённой обратной связью

Регистр сдвига с обобщённой обратной связью (англ. Generalized feedback shift register (GFSR)) — вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Теодором Льюисом и Уильямом Пейном[англ.] в 1973 году.

Cхема регистра сдвига с обобщённой обратной связью

Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига с линейной обратной связью , основанная на примитивном трёхчлене , записывается в колонок, , с разумно выбранными циклическими сдвигами. и  — произвольные натуральные числа, такие что , причём примерно равных и , нужно избегать из-за плохих свойств результирующей последовательности.[1]

Таким образом все слова на выходе GFSR можно рассматривать как вектора длины , с коэффициентами из множества , которые подчиняются рекурсии

где  — XOR, или побитовое сложение по модулю 2, а [2]

Сравнение с аналогичными алгоритмами

Результат работы линейного конгруэнтного генератора

Линейный конгруэнтный генератор показывает плохую n-пространственную однородность. На рисунке предвиден пример результата работы для для 384 точек (a) и 512 (b).[1]

Результат работы GFSR

Как альтернатива, регистр сдвига с линейной обратной связью (FSR) даёт равномерное распределение в n-мерном пространстве, если длина регистра делится на n. Возможно FSR последовательности дают больше возможностей для улучшения n-мерного пространства, но период ограничен машинным словом. Кроме того, прореживание, с целью получить однородность n-мерном пространстве далее сокращает длину цикла.[1]

Из-за этого был создан регистр сдвига с обобщённой обратной связью, способный генерировать сколь угодно большие последовательности, независимо от размера машинного слова, также обладающий хорошим n-мерным распределением и большой скоростью.[1]

На рисунке предвиден пример результата работы GFSR c полиномом , 9-битным машинным словом и циклическим сдвигом на 93[1]

История исследования GFSR

Льюисом и Пейном были представлены различные типы генераторов называемые регистры сдвига с обобщённой обратной связью. Этот быстрый метод и может генерировать одинаковые последовательности на компьютерах с разной длиной машинного слова, но он имеет недостаток с инициализацией.[3]

Во-первых, невырожденная битовая начальная матрица размером должна быть сформирована. Льюис и Пейн показали, что если относительный сдвиг между соседними колонками постоянен, то матрица не вырожденная. Постоянный сдвиг был произвольно выбран равным .[3]

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

Другой недостаток который может быть более существенным, нет теоретического обоснования того, что последовательность будет обладать свойством k-распределения. Термин k-распределение означает, что каждый k-кортеж из -бит чисел появляется раз на полном периоде, за исключением нулевого кортежа. Они показали что последовательность может быть k-распределённая, для , но это необходимое, а не достаточное условие.[3]

Брайт (Bright) и Энисон (Enison) провели тесты на равнораспределение в пространствах большой размерности небольшой части последовательности с большим периодом. Оказалось что в тестах статистические свойства не повторяют свойства всей последовательности.[3]

Арвилиас (Arvillias) и Маритсас (Maritsas) предложили генератор типа GFSR, в которых есть степень 2. Они показали что элементов последовательности, почти равномерно распределённых вдоль периода, можно получить за один такт, используя переключатель и регистры сдвига. При этом относительный сдвиг аналитически определён. Это значит, что процесс инициализации становится столь же быстрым как и генерация случайных чисел. Но снова нет гарантий в k-распределении.[3]

Алгоритм GFSR

Входные значения:

  •  — задают характеристический полином регистра сдвига
  •  — начальная битовая последовательность

Алгоритм:

1. Создаем массив битовых векторов , по которому будем перемещаться с индексом и вспомогательным индексом .
2. Инициализируем массив, используя начальную битовую последовательность. Устанавливаем равное 0.
3. Вычисляем следующий вектор, но так как массив длины , то индексы вычисляются по модулю , из-за чего
Таким образом
4. Увеличиваем на единицу и переходим к вычислению следующего вектора, до тех пор пока последовательность не начнет повторяться (длина последовательности )[1]

Алгоритм инициализации

  1. Сначала генерируется последовательность согласно алгоритму регистра сдвига с линейной обратной связью.
  2. После чего полученная последовательность циклически сдвигается. Величина сдвига должна быть меньше периода , тогда гарантируется что стартовые вектора будут линейно независимы (если величина сдвига взаимно просто с , то сдвиг может превышать полный период).
  3. Используя эту процедуру, получаем последовательностей, которые можно записать друг под другом. Первые бит последовательностей образуют матрицу, столбцы которой являются векторами [1]

Пример

Пусть дан полином , и .

Элементы последовательности удовлетворяют равенству при . Согласно полиному , так мы можем узнать элементы последовательности

и так далее.

Таким образом получаем последовательность

Для того чтобы создать хорошую случайную последовательность воспользуемся алгоритмом Кендола (Kendall). Хотя есть несколько вариантов этого алгоритма мы возьмем тот, который сдвигает начальную последовательность 1111100011011101010000100|101100 вперед на 6 бит. То есть 1011001111100011011101010|000100 и так ещё 3 раза. Таким образом получим

Номер последовательность
0 1111100011011101010000100101100
1 1011001111100011011101010000100
2 0001001011001111100011011101010
3 1010100001001011001111100011011
4 0110111010100001001011001111100

образуется из первых бит последовательностей,  — из вторых, для аналогично.

Последующие вычисляем согласно правилу .

11010 01001 00111
10001 10000 01111
11011 10110 10010
11100 10100 01100
10011 01110 00101
00001 11111 10101
01101 00100 00011
01000 11000 10111
11101 01011 11001
11110 01010 00110

Преимущества и недостатки

Преимущества

По словам разработчиков регистр сдвига с обобщённой обратной связью обладает произвольно большим периодом, независимо от длины машинного слова компьютера, который выполняет алгоритм, он быстрее чем другие генераторы псевдослучайных последовательностей, а также алгоритм легок в реализации.[1]

Недостатки

Согласно исследованиям количество 0 и 1 в выходной последовательности заметно разнится, а что противоречит постулатам Голомба. Также, если взять целое N, и разделить последовательность на кортежи по N слов, то для случайной последовательности распределение единиц в этих кортежах должно подчиняться биномиальному распределению Bin(N, 1/2). Но оказалось, что при это условие не выполняется. Это из-за того, что каждое слово зависит только от двух предыдущих, и по этому преобладание единиц или нулей не «сглаживается» сумматором по модулю 2.[2]

Вихрь Мерсенна — пример улучшения GFSR

Широко известна модификация регистра сдвига с обобщённой обратной связью под названием «Вихрь Мерсенна», предложенный Макото Мацумото и Такудзи Нисимурой в 1997 году. Период этого генератора огромен, и равен числу Мерсенна . Вихрь Мерсенна относят к классу витковых генераторов на регистрах сдвига с обобщёнными обратными связями. Его упрощённая схема приведена на рисунке

Упрощённая схема вихря Мерсенна

Рассмотрим наиболее распространённый вариант этого алгоритма — MT19937. Он использует 624 ячейки памяти, в каждой из которых содержится целое 32 битное число. При этом рекуррентное правило формирования последовательности выходных слов записывается таким образом:

& 0x80000000) | & 0x7fffffff))×, (i = 0, 1 , 2, …)

То есть, на каждом k-том шаге берётся старший бит слова , и 31 бит из слова , а затем полученные части конкатенируют с последующим умножением полученного результата на матрицу

где = 0x9908B0DF в шестнадцатеричном исчислении.

После этого, результат складывается по модулю 2 со словом, вычисленного на предыдущем 397-м шаге. Затем делается сдвиг содержимого всех ячеек на шаг влево, и полученный результат записывается в освободившуюся ячейку.[2]

См. также

Литература

  • T. G. Lewis, W. H. Payne. Journal of the ACM (JACM) Volume 20 Issue 3. — NY: ACM, July 1973.
  • James E. Gentle. Random number generation and Monte carlo methods. — 2nd edition. — NY: Springer, 2003. — XV + 381 с. — ISBN 0-387-00178-6.

Примечания

  1. 1 2 3 4 5 6 7 8 T. G. Lewis, W. H. Payne. Generalized Feedback Shift Register Pseudorandom Number Algorithm // J. ACM. — 1973-07-01. — Т. 20, вып. 3. — С. 456–468. — ISSN 0004-5411. — doi:10.1145/321765.321777.
  2. 1 2 3 Н. Ф. Казакова, к.т.н., Ю. В. Щербина, к.т.н. ПРОБЛЕМЫ ОЦЕНКИ КАЧЕСТВА РАБОТЫ СОВРЕМЕННЫХ ЛИНЕЙНЫХ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ (рус.) // Збірник наукових праць ОДАТРЯ No 1(2 )2013. Архивировано 23 марта 2022 года.
  3. 1 2 3 4 5 M. Fushimi, S. Tezuka. The k-distribution of generalized feedback shift register pseudorandom numbers // Communications of the ACM. — 1983-07-01. — Т. 26, вып. 7. — С. 516–523. — ISSN 0001-0782. — doi:10.1145/358150.358159. Архивировано 16 ноября 2016 года.

Ссылки

Read other articles:

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Andika Naliputra – berita · surat kabar · buku · cendekiawan · JSTOR Biografi ini tidak memiliki sumber tepercaya sehingga isinya tidak dapat dipastikan. Bantu memperbaiki artikel ini dengan menambahkan ...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Artyom ZhmakinInformasi pribadiNama lengkap Artyom Ivanovich ZhmakinTanggal lahir 10 September 1995 (umur 28)Tinggi 1,74 m (5 ft 8+1⁄2 in)Posisi bermain GelandangInformasi klubKlub saat ini FC Avangard KurskKarier senior*Tahu...

 

Kantor Perserikatan Bangsa-Bangsa di JenewaPalais des Nations, gedung utama Kantor Perserikatan Bangsa-Bangsa di JenewaUNOGLokasi di SwissNama lainUNOGInformasi umumKotaJenewaNegara SwissKoordinat46°13′36″N 6°08′26″E / 46.226667°N 6.140556°E / 46.226667; 6.140556Koordinat: 46°13′36″N 6°08′26″E / 46.226667°N 6.140556°E / 46.226667; 6.140556Situs webwww.unog.ch Palais des Nations, bangunan utama Kantor PBB di Jenewa. Pada 2...

Jérusalem-Est Administration Pays Palestine Israël Gouvernorat palestinien Jérusalem Démographie Population 542 400 hab. (2016) Géographie Coordonnées 31° 47′ nord, 35° 14′ est Localisation Géolocalisation sur la carte : Israël Jérusalem-Est Géolocalisation sur la carte : Palestine Jérusalem-Est modifier  Jérusalem-Est (en arabe : Al-Quds ash-Sharqiya ; en hébreu romanisé : Mizraa Yerushalayim) est le secteur de ...

 

Fictional character in A Song of Ice and Fire novels Fictional character Jaime LannisterA Song of Ice and Fire character Game of Thrones characterNikolaj Coster-Waldau as Jaime LannisterFirst appearance Literature: A Game of Thrones (1996) Television: Winter Is Coming (2011) Last appearance Television: The Iron Throne (2019) Created byGeorge R. R. MartinAdapted byDavid Benioff D. B. Weiss (Game of Thrones)Portrayed byNikolaj Coster-WaldauIn-universe informationAliasesThe KingslayerThe Young L...

 

Questa voce o sezione sugli argomenti stati scomparsi e Germania non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti dei progetti di riferimento 1, 2. Brandeburgo Informazioni generaliNome ufficialeLand Brandenburg CapoluogoPotsdam 118.180 abitanti (1950) Dipendente da Zona sovietica (1946-1949) Germania Est (1949-1952) Evoluzione storic...

Not to be confused with octane or octyne. 1-octene Octene is an alkene with the formula C8H16. Several isomers of octene are known, depending on the position and the geometry of the double bond in the carbon chain. The simplest isomer is 1-octene, an alpha-olefin used primarily as a co-monomer in production of polyethylene via the solution polymerization process. Several useful structural isomers of the octenes are obtained by dimerization of isobutene and 1-butene. These branched alkenes are...

 

NFL team season 1983 St. Louis Cardinals seasonOwnerBill BidwillHead coachJim HanifanHome fieldBusch StadiumResultsRecord8–7–1Division place3rd NFC EastPlayoff finishDid not qualifyPro BowlersWR Roy GreenP Carl Birdsong ← 1982 Cardinals seasons 1984 → The 1983 St. Louis Cardinals season was the 64th season the team was in the National Football League. The Cardinals won eight games, including victories over both participants in that year's AFC Championship Game, ...

 

State highway in Pennsylvania, US Pennsylvania Route 23Route informationMaintained by PennDOT, City of Lancaster, Upper Merion Township, and Lower Merion TownshipLength81.144 mi[1] (130.589 km)Existed1928–presentTouristroutesConestoga Ridge BywayMajor junctionsWest end PA 441 in MariettaMajor intersections US 222 in Lancaster US 30 east of Lancaster US 322 in Blue Ball I-176 in Morgantown PA 10 in Morgantown PA 100 in Bucktown PA...

Sachuest Point National Wildlife RefugeIUCN category IV (habitat/species management area)Map of Rhode IslandLocationNewport County, Rhode Island, United StatesNearest cityMiddletown, Rhode IslandCoordinates41°28′47″N 71°14′28″W / 41.47982°N 71.24115°W / 41.47982; -71.24115[1]Area242 acres (0.98 km2)Established1970Governing bodyU.S. Fish and Wildlife ServiceWebsiteSachuest Point National Wildlife Refuge Sachuest Point National Wildlife...

 

Джон ПолкинхорнJohn Polkinghorne Имя при рождении англ. John Charlton Polkinghorne[1] Дата рождения 16 октября 1930(1930-10-16) Место рождения Уэстон-сьюпер-Мэр, Сомерсет, Англия, Великобритания Дата смерти 9 марта 2021(2021-03-09) (90 лет) Место смерти Кембридж, Англия, Великобритания Страна  Великоб...

 

Census-designated place in TexasWest Sharyland, TexasCensus-designated placeCoordinates: 26°16′37″N 98°20′18″W / 26.27694°N 98.33833°W / 26.27694; -98.33833Country United States of AmericaState TexasCounty HidalgoArea • Total2.3 sq mi (6.0 km2) • Land2.3 sq mi (6.0 km2) • Water0.0 sq mi (0.0 km2)Elevation171 ft (52 m)Population (2010)[1] �...

List of U.S Events in 2022 ← 2021 2020 2019 2022 in the United States → 2023 2024 2025 Decades: 2000s 2010s 2020s 2030s See also: History of the United States (2008–present) Timeline of United States history (2010–present) List of years in the United States 2022 in the United States2022 in U.S. states and territories States Alabama Alaska Arizona Arkansas California Colorado Connecticut Delaware Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas Kentucky Louisiana Maine...

 

  لمعانٍ أخرى، طالع كلية الأعمال (توضيح). كلية الأعمال شعار كلية الأعمال (الجامعة الأردنية)شعار الكلية جانب من الجهة الشمالية لمباني الكلية. الشعار موطن التميز وطريق النجاح.[1] معلومات التأسيس 1965 النوع كلية جامعية حكومية الشُعب سبعة أقسام الموقع الجغرافي إحداثيات 3...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. Conizonia simia Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Cerambycidae Genus: Conizonia Spesies: Conizonia simia Conizonia simia adalah spesies kumbang tanduk panjang yang tergolong famili Cerambyc...

Artículo principal: Audax Italiano Luis Cabrera utilizando el uniforme titular de Audax Italiano durante la temporada 2020, conmemorativo de los 110 años de la institución. La Indumentaria de Audax Italiano es el utilizado por los jugadores «Itálicos» tanto en competencias nacionales como internacionales, desde el primer equipo hasta los juveniles, como también la Femenil. La vestimenta titular histórica usada por el club consta de camiseta verde, pantalón blanco y medias verdes...

 

安德烈·薩全名André Sá國家/地區 巴西居住地 巴西布盧梅瑙出生 (1977-05-06) 1977年5月6日(47歲) 巴西贝洛奥里藏特身高185體重74轉職業年1996年持拍右手手持拍(雙手反拍)職業獎金2,083,692美元單打成績職業戰績52勝92負(單打)202勝206負(雙打)冠軍頭銜0最高排名55(2002年8月12日)大滿貫單打成績澳網男雙八強(2004)法網男雙第三輪(2002)溫網男雙四強(2007)美�...

 

Miguel Ángel Asturias Información personalNombre de nacimiento Miguel Ángel Asturias RosalesNacimiento 19 de octubre de 1899Ciudad de Guatemala, GuatemalaFallecimiento 9 de junio de 1974 (74 años)Madrid, EspañaSepultura Cementerio del Père-Lachaise y Grave of Miguel Ángel Asturias Nacionalidad GuatemaltecoReligión CatolicismoFamiliaCónyuge Clemencia AmadoBlanca Mora y AraujoHijos Rodrigo Asturias Amado, Miguel Ángel Asturias AmadoEducaciónEducado en Escuela Facultativa de Derecho d...

Newspaper in Denver, Colorado For the Alberta publication WestWord, see Writers Guild of Alberta. Not to be confused with Westworld. WestwordTypeAlternative weeklyFormatMagazineOwner(s)Voice Media GroupPublisherScott TobiasEditorPatricia CalhounFounded1977; 47 years ago (1977)Headquarters1278 Lincoln St, Denver, Colorado, 80203, USACirculation67,520 (as of 2014)[1]Websitewestword.com Westword is a free digital and print media publication based in Denver, Colorado...

 

The Cross of Mathildel 中世のカトリック教会は教会国家という世俗的な基盤を有しながらも、全ヨーロッパ規模での普遍的な権威を主張した。近代ヨーロッパ各地に国民国家が成立していくと教皇領は世俗国家に回収された。現在ローマ教皇庁は独立国家バチカン市国にある。 中世ヨーロッパ史においては、西欧諸国の学界においても日本の学界においても「教会と国家」�...