Сызықтық кері байланыс тіркегіштері (LFSR) – есептеуде қолданылатын, XOR функциясымен жұмыс істейтін тіркегіштер. Бастапқы мәнінен циклды тізбек құрады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеудегі ауысу тізілімінің түрі
Type of shift register in computing
Есептеуде сызықтық кері байланыс ауысу тізілімі (LFSR) – кіріс биті оның алдыңғы күйінің сызықтық функциясы болып табылатын ауысу тізілімі. Жеке биттердің ең көп қолданылатын сызықтық функциясы – эксклюзивті немесе (XOR). Осылайша, LFSR көбінесе кіріс биті ауысу тізілімінің жалпы мәнінің кейбір биттерінің XOR-ымен басқарылатын ауысу тізілімі болып табылады. LFSR-дің бастапқы мәні – тұқым деп аталады, ал тізілімнің жұмысы детерминистік болғандықтан, тізілім шығаратын мәндер тізбегі оның қазіргі (немесе бұрынғы) күйімен толығымен анықталады. Сондай-ақ, тізілімдегі мүмкін болатын күйлер саны шектеулі болғандықтан, ол сөзсіз қайталанатын циклға енеді. Дегенмен, жақсы таңдалған кері байланыс функциясы бар LFSR кездейсоқ көрінетін және өте ұзақ циклға ие биттер тізбегін жасауға қабілетті. LFSR-дің қолданылуына псевдокезеңсіз сандарды, псевдошу тізбектерін, жылдам цифрлық санағыштарды және ақтандыру тізбектерін жасау жатады. LFSR-дің аппараттық және бағдарламалық құралдары кеңінен таралған. Жіберу қателерін жылдам тексеруге қолданылатын циклдық артықтық тексерудің математикасы LFSR-мен тығыз байланысты. Жалпы алғанда, LFSR-дің артындағы арифметика оларды зерттеу және іске асыру үшін өте тартымды нысанға айналдырады. Қарапайым құрылымдық элементтерді пайдаланып салыстырмалы түрде күрделі логикалық схемаларды құруға болады. Алайда, басқа әдістер де қарастырылуы керек, олар бәлкім, азырақ тартымды болғанымен, жақсы нәтижелер береді.
In computing, a linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive or (XOR). Thus, an LFSR is most often a shift register whose input bit is driven by the XOR of some bits of the overall shift register value. The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, an LFSR with a well chosen feedback function can produce a sequence of bits that appears random and has a very long cycle. Applications of LFSRs include generating pseudo random numbers, pseudo noise sequences, fast digital counters, and whitening sequences. Both hardware and software implementations of LFSRs are common. The mathematics of a cyclic redundancy check, used to provide a quick check against transmission errors, are closely related to those of an LFSR. In general, the arithmetics behind LFSRs makes them very elegant as an object to study and implement. One can produce relatively complex logics with simple building blocks. However, other methods, that are less elegant but perform better, should be considered as well.
Бинарлық емес Galois LFSR
Жоғарыда көрсетілгендей, екілік Галлои LFSR-лары кез келген q-дық алфавитке {0, 1, ..., q-1} обобщается алады (мысалы, екілік үшін q = 2, ал алфавит жай ғана {0, 1}). Бұл жағдайда, эксклюзивті немесе компоненті q модулі бойынша қосуға обобщается (XOR-дың 2 модулі бойынша қосу екенін ескеріңіз), ал кері байланыс биті (шығыс биті) әрбір нақты түйіспе нүктесі үшін тұрақты болатын q-дық мәнмен көбейтіледі (q модулі бойынша). Бұл екілік жағдайдың да обобщалануы болып табылады, онда кері байланыс 0-ге көбейтіледі (кері байланыс жоқ, яғни түйіспе жоқ) немесе 1-ге (кері байланыс бар). Тиісті түйіспе конфигурациясы болған жағдайда, мұндай LFSR-ларды q-ның кез келген жай мәні үшін Галуа өрістерін жасау үшін пайдалануға болады.
Binary Galois LFSRs like the ones shown above can be generalized to any q ary alphabet {0, 1, , q − 1} (e. g., for binary, q = 2, and the alphabet is simply {0, 1}). In this case, the exclusive or component is generalized to addition modulo q (note that XOR is addition modulo 2), and the feedback bit (output bit) is multiplied (modulo q) by a q ary value, which is constant for each specific tap point. Note that this is also a generalization of the binary case, where the feedback is multiplied by either 0 (no feedback, i. e., no tap) or 1 (feedback is present). Given an appropriate tap configuration, such LFSRs can be used to generate Galois fields for arbitrary prime values of q.
Шығыс ағынының қасиеттері
Бірлер мен нөлдер "тізбектер" түрінде кездеседі. Мысалы, 1110010 шығыс ағыны 3, 2, 1, 1 ұзындығындағы төрт тізбектен тұрады. Максималды LFSR-дің бір периодында 2n-1 тізбек кездеседі (жоғарыдағы мысалда 3 биттік LFSR 4 тізбекке ие). Осы тізбектердің жартысы бір биттен, төрттен бірі екі биттен тұрады, содан кейін нөлдердің бір тізбегі n-1 биттен және бірліктердің бір тізбегі n биттен құралады. Бұл таралым нағыз кездейсоқ тізбек үшін күтілетін статистикалық мәнге жақын. Дегенмен, нағыз кездейсоқ тізбек үлгісінде осы таралымды табу ықтималдығы өте төмен. LFSR шығыс ағыны детерминистік болып табылады. Егер LFSR-дегі XOR қақпаларының ағымдағы күйі мен орналасуы белгілі болса, келесі күйді болжауға болады. Бұл нағыз кездейсоқ оқиғалар үшін мүмкін емес. Максималды ұзындығы бар LFSR-лерде келесі күйді есептеу әлдеқайда оңай, себебі әр ұзындық үшін олардың саны шектеулі. Шығыс ағыны қайтымды; айналдырылған LFSR шығыс тізбегін кері ретпен өтеді. Барлық нөлдерден тұратын мән пайда бола алмайды. Осылайша, n ұзындығындағы LFSR барлық 2n мәнін жасау үшін қолданыла алмайды.
Ones and zeroes occur in "runs". The output stream 1110010, for example, consists of four runs of lengths 3, 2, 1, 1, in order. In one period of a maximal LFSR, 2n−1 runs occur (in the example above, the 3 bit LFSR has 4 runs). Exactly half of these runs are one bit long, a quarter are two bits long, up to a single run of zeroes n − 1 bits long, and a single run of ones n bits long. This distribution almost equals the statistical expectation value for a truly random sequence. However, the probability of finding exactly this distribution in a sample of a truly random sequence is rather low. LFSR output streams are deterministic. If the present state and the positions of the XOR gates in the LFSR are known, the next state can be predicted. This is not possible with truly random events. With maximal length LFSRs, it is much easier to compute the next state, as there are only an easily limited number of them for each length. The output stream is reversible; an LFSR with mirrored taps will cycle through the output sequence in reverse order. The value consisting of all zeros cannot appear. Thus an LFSR of length n cannot be used to generate all 2n values.
Қолданбалар
LFSR-лер аппараттық түрде жүзеге асырылуы мүмкін, бұл оларды псевдокезеңсіз тізбектің өте жылдам жасалуын қажет ететін қолданыстарда, мысалы, тікелей реттілікпен таралатын радиоспектрде пайдалы етеді. LFSR-лер сонымен қатар әртүрлі бағдарламаланатын дыбыс генераторларында ақ шудың жуықтауын жасау үшін де қолданылған.
LFSRs can be implemented in hardware, and this makes them useful in applications that require very fast generation of a pseudo random sequence, such as direct sequence spread spectrum radio. LFSRs have also been used for generating an approximation of white noise in various programmable sound generators.
Есептеу ретінде пайдалану
LFSR-дің қайталамалы күйлер тізбегі оны сағатты бөлуге немесе бинарлық емес тізбектерге рұқсат етілген жағдайларда, есептегіш ретінде қолдануға мүмкіндік береді, әсіресе компьютерлік индекс немесе кадрлық орналасулар машинамен оқылғанда. LFSR-дің үзілісті сағатталуы, мысалы, ауыспалы қадам генераторындағыдай. LFSR негізіндегі маңызды ағын шифрларына GSM ұялы телефондарында қолданылатын A5/1 және A5/2, Bluetooth-та қолданылатын E0 және қысқарту генераторы жатады. A5/2 шифры бұзылған, ал A5/1 және E0 шифрларында елеулі әлсіздіктер бар. Сызықтық кері байланыс тізбектік тіркегі сызықтық конгруенциялық генераторлармен тығыз байланыста.
The repeating sequence of states of an LFSR allows it to be used as a clock divider or as a counter when a non binary sequence is acceptable, as is often the case where computer index or framing locations need to be machine readable. Irregular clocking of the LFSR, as in the alternating step generator. Important LFSR based stream ciphers include A5/1 and A5/2, used in GSM cell phones, E0, used in Bluetooth, and the shrinking generator. The A5/2 cipher has been broken and both A5/1 and E0 have serious weaknesses. The linear feedback shift register has a strong relationship to linear congruential generators.
Сұлбаларды сынаудағы қолданылу
LFSR-лер тізбектерді сынау үшін сынақ үлгісін жасау (толық сынау, псевдорандомды сынау немесе псевдотолық сынау үшін) және қолтаңба талдау үшін қолданылады.
LFSRs are used in circuit testing for test pattern generation (for exhaustive testing, pseudo random testing or pseudo exhaustive testing) and for signature analysis.
Сынақ үлгісін жасау
Толық LFSR-лер көлемді сынақтар үшін үлгі генераторлары ретінде жиі қолданылады, себебі олар n кірістік тізбек үшін барлық мүмкін кіріс комбинацияларын қамтиды. Максималды ұзындығы бар LFSR және салмақталған LFSR псевдокезеңдік сынақ қолданбаларында псевдокезеңдік тесттік үлгілерді жасау үшін кеңінен пайдаланылады.
Complete LFSR are commonly used as pattern generators for exhaustive testing, since they cover all possible inputs for an n input circuit. Maximal length LFSRs and weighted LFSRs are widely used as pseudo random test pattern generators for pseudo random test applications.
Қолтаңба талдау
Өзін-өзі сынау (BIST) әдістерінде барлық схема шығыстарын чипке сақтау мүмкін емес, бірақ схема шығысын кейіннен ақауларды анықтау үшін «алтын қолтаңбамен» (жақсы схеманың) салыстыруға болатын қолтаңбаны құру үшін жинақылауға болады. Бұл жинақылау жоғалтулы болғандықтан, әрқашан қателі шығыс та алтын қолтаңбамен бірдей қолтаңбаны тудыруы және ақауларды анықтау мүмкін болмауы мүмкін. Бұл жағдай қателерді жасыру немесе алиастық эффект деп аталады. BIST көп кірісті қолтаңба тіркегішімен (MISR немесе MSR) іске асырылады, ол LFSR түрі. Стандартты LFSR бір XOR немесе XNOR қақпасына ие, онда қақпаның кірісі бірнеше «тежегіштерге» қосылады, ал шығысы бірінші триггердің кірісіне қосылады. MISR-дің құрылымы ұқсас, бірақ әрбір триггерге кіретін дерек XOR/XNOR қақпасы арқылы өтеді. Мысалы, 4 биттік MISR 4 биттік параллель шығысқа және 4 биттік параллель кіріске ие. Бірінші триггердің кірісі XOR/XNOR арқылы параллель кіріс битінің нөлімен және «тежегіштермен» байланыстырылады. Әрбір келесі триггердің кірісі XOR/XNOR арқылы алдыңғы триггердің шығысымен және сәйкес келетін параллель кіріс битімен байланыстырылады. Осылайша, MISR-дің келесі күйі тек қана ағымдағы күйге емес, соңғы бірнеше күйлерге де байланысты болады. Сондықтан, кіріс тізбегі әрқашан бірдей болса, MISR әрқашан бірдей алтын қолтаңбаны тудырады. Жақындағы қолданбалар LFSR «тежегіштері» ретінде қосымша резеңке триггерлерін ұсынады. Бұл BIST жүйесіне жадты оңтайландыруға мүмкіндік береді, себебі қосымша резеңке триггерлер LFSR-ден барлық биттер ағынын құру үшін бастапқы тұқымды сақтай алады. Дегенмен, бұл BIST архитектурасын өзгертуді талап етеді және белгілі бір қолданбалар үшін ғана қолданылатын опция болып табылады.
In built in self test (BIST) techniques, storing all the circuit outputs on chip is not possible, but the circuit output can be compressed to form a signature that will later be compared to the golden signature (of the good circuit) to detect faults. Since this compression is lossy, there is always a possibility that a faulty output also generates the same signature as the golden signature and the faults cannot be detected. This condition is called error masking or aliasing. BIST is accomplished with a multiple input signature register (MISR or MSR), which is a type of LFSR. A standard LFSR has a single XOR or XNOR gate, where the input of the gate is connected to several "taps" and the output is connected to the input of the first flip flop. A MISR has the same structure, but the input to every flip flop is fed through an XOR/XNOR gate. For example, a 4 bit MISR has a 4 bit parallel output and a 4 bit parallel input. The input of the first flip flop is XOR/XNORd with parallel input bit zero and the "taps". Every other flip flop input is XOR/XNORd with the preceding flip flop output and the corresponding parallel input bit. Consequently, the next state of the MISR depends on the last several states opposed to just the current state. Therefore, a MISR will always generate the same golden signature given that the input sequence is the same every time. Recent applications are proposing set reset flip flops as "taps" of the LFSR. This allows the BIST system to optimise storage, since set reset flip flops can save the initial seed to generate the whole stream of bits from the LFSR. Nevertheless, this requires changes in the architecture of BIST, is an option for specific applications.
Басқа қолданыстар
LFSR-лер радио бұғаттау жүйелерінде де мақсатты коммуникациялық жүйенің шу деңгейін көтеру үшін псевдокезеңдік шуды жасауға қолданылады. Неміс уақыт сигналы DCF77, амплитудалық модуляциямен қатар, қабылданған уақыттың дәлдігін және шудың әсеріне қарсы дерек ағынының тұрақтылығын арттыру үшін 9 сатылы LFSR-мен басқарылатын фазалық модуляцияны пайдаланады.
LFSRs are also used in radio jamming systems to generate pseudo random noise to raise the noise floor of a target communication system. The German time signal DCF77, in addition to amplitude keying, employs phase shift keying driven by a 9 stage LFSR to increase the accuracy of received time and the robustness of the data stream in the presence of noise.