| dbo:abstract
|
- Posuvný registr s lineární zpětnou vazbou (anglicky linear-feedback shift register, zkratkou LFSR) je posuvný registr, jehož výstup je lineárně závislý na jeho předchozích výstupech a stavu. Posuvné registry s lineární zpětnou vazbou jsou oblíbené jako generátory pseudonáhodných čísel a také v kryptografii jako součásti proudových šifer. Jejich výstup je kromě zpětnovazební funkce závislý také na jejich počátečním stavu, který se v případě použití jako generátorů pseudonáhodných čísel nazývá semínko (v případě šifrového použití je odvozený z klíče). Posuvné registry s lineární zpětnou vazbou je možné implementovat hardwarově i softwarově. Nejběžnější je registr složený z jednotlivých bitů, tedy lineární funkce je počítána nad dvouprvkovým tělesem, kde operace sčítání odpovídá exkluzivnímu součtu. (cs)
- LFSR significa linear feedback shift register, que es tradueix com: registre de desplaçament amb retroalimentació lineal. És un registre de desplaçament en el qual l'entrada és un bit provinent d'aplicar una funció de transformació lineal a un estat anterior. El valor inicial es denomina llavor i, com la forma d'operar el registre és determinística, la seqüència de valors produïts està completament determinada per l'estat actual o l'estat anterior. La seqüència té un període de repetició, és a dir que la seqüència torna a generar i es repeteix indefinidament. Quan el període de repetició és màxim, aquest LFSR té interès criptogràfic. (ca)
- Ein linear rückgekoppeltes Schieberegister (engl. linear feedback shift register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, das zur Erzeugung von streng deterministischen Pseudozufallszahlenfolgen eingesetzt werden kann. Zur Rückkopplung wird die lineare logische Funktion XOR verwendet. Den Startwert bezeichnet man als seed. Da die Ausgabe des Registers streng deterministisch ist und vollständig von seinem momentanen Zustand abhängt, das Register jedoch gleichzeitig nur eine endliche Anzahl an Zuständen hat, muss es zwangsläufig irgendwann wieder bei seinem Startwert ankommen. Bei n Bit breiten Schieberegistern ergibt sich damit eine maximale Periodenlänge von 2n−1. Ab diesem Zeitpunkt wiederholt sich die Ausgabesequenz, das Register befindet sich in einem Wiederholzyklus. Je nach gewählter Implementierung ist diese Sequenz unterschiedlich lang, allerhöchstens können Folgen maximaler Länge erzeugt werden. Anwendungen liegen neben der Erzeugung von Pseudozufallszahlenfolgen im Bereich schneller digitaler Synchronzähler, da diese Zähler ohne Übertrag arbeiten, im Bereich der Nachrichtentechnik und Kryptografie bei Scramblern, um Datenfolgen spektral weiß zu machen, in der Kodierungstheorie bei der Kodierung und Dekodierung von zyklischen Codes, wie beispielsweise bei der zyklischen Redundanzprüfung (CRC) oder dem Hamming-Code, und im Bereich der digitalen Modulationstechnik bei den Codemultiplexverfahren (CDMA) und im Bereich der Steganographie. Linear rückgekoppelte Schieberegister können effizient sowohl direkt in Hardware, wie beispielsweise FPGAs, als auch in Software implementiert werden. Bei der Softwareimplementierung wird, da die meisten Prozessoren mit Registerbreiten größer als ein Bit arbeiten, typischerweise mit im Voraus berechneten Tabellen gearbeitet, die direkt den inneren Zustand des Schieberegisters abbilden. (de)
- LFSR significa linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior. El valor inicial se denomina semilla y, como la forma de operar el registro es determinista, la secuencia de valores producidos está completamente determinada por el estado actual o el estado anterior. La secuencia tiene un periodo de repetición, es decir que la secuencia vuelve a generarse y se repite indefinidamente. Cuando el periodo de repetición es máximo, ese LFSR tiene interés criptográfico. (es)
- 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. (en)
- Un registre à décalage à rétroaction linéaire, ou LFSR (sigle de l'anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite de bits qui peut être vue comme une suite récurrente linéaire sur le corps fini F2 à 2 éléments (0 et 1). La notion a été généralisée à n'importe quel corps fini. Réalisé électroniquement, dans le cas particulier d'une suite de 0 et de 1, c'est un registre à décalage avec rétroaction linéaire, ce qui signifie que le bit entrant est le résultat d'un OU exclusif (ou XOR) entre plusieurs bits du registre, cette opération étant également l'addition sur le corps fini F2. Ces dispositifs sont simples, peu coûteux et efficaces. La suite récurrente produite par un LFSR est nécessairement périodique à partir d'un certain rang. Les LFSR sont utilisés en cryptographie pour engendrer des suites de nombres pseudo-aléatoires. La fonction de rétroaction est alors choisie de façon à obtenir une période la plus grande possible. L’étendue des applications est très large : chiffrement des communications, contrôle d'erreurs sur la transmission de données, auto-test des composants électroniques… (fr)
- Il registro a scorrimento a retroazione lineare (linear feedback shift register, LFSR) è una tipologia di registri di traslazione i cui dati in ingresso sono prodotti da una funzione lineare dello stato interno. Le uniche funzioni lineari di singoli bit sono lo XOR e lo XNOR (xor inverso); perciò è un registro di traslazione i cui bit in ingresso sono prodotti dall'or esclusivo (xor) di alcuni bit memorizzati all'interno dei registri. Il valore iniziale di un LFSR è chiamato seme, e poiché l'operazione del registro è deterministica, la sequenza di valori prodotta dal registro è completamente determinata dal suo stato corrente o precedente. Allo stesso modo, poiché il registro ha un numero finito di stati possibili, prima o poi i valori in uscita si ripetono; ciò nonostante, un LFSR con una funzione di retroazione ben scelta può produrre una sequenza di bit che appare casuale ed ha un periodo molto lungo. Applicazioni degli LFSR includono la generazione di numeri pseudo-casuali, sequenze pseudo-rumore (approssimazione del rumore bianco) e contatori digitali. Sono comuni implementazioni sia in hardware che in software. (it)
- 선형 되먹임 시프트 레지스터(Linear feedback shift register, LFSR)는 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되는 구조를 가지고 있다. 이때 사용되는 선형 함수는 주로 배타적 논리합(XOR)이다. LFSR의 초기 비트 값은 시드(seed)라고 부른다. LFSR의 동작은 결정론적이기 때문에, LFSR로 생성되는 값의 수열은 그 이전 값에 의해 결정된다. 또한, 레지스터가 가질 수 있는 값의 개수는 유한하기 때문에, 이 수열은 특정한 주기에 의해 반복된다. 하지만 선형 함수를 잘 선택한다면 주기가 길고 무작위적으로 보이는 수열을 생성할 수 있다. LFSR는 의사 난수, (PRN), 빠른 디지털 카운터, 백지화 수열 등의 분야에서 사용된다. (ko)
- 線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、英: linear feedback shift register, LFSR）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。 値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。 LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。 LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。 (ja)
- Een linear feedback shift register, afgekort LFSR, is een schuifregister dat als belangrijkste kenmerk heeft dat bepaalde uitgangen via een xor-bewerking teruggekoppeld worden naar de ingang van het schuifregister. Het schuifregister is op deze manier in staat een rij bits te genereren. De lengte van de gegenereerde rij hangt af van welke uitgangen teruggekoppeld zijn, en is maximaal , met de lengte van het schuifregister (een ), of als met extra logica nul gedetecteerd wordt. Een belangrijk kenmerk van de rij is dat elk getal maar één keer voorkomt. De bits in het schuifregister worden in ieder geval vanaf een bepaalde combinatie cyclisch doorlopen. (nl)
- Rejestr przesuwający z liniowym sprzężeniem zwrotnym (ang. linear feedback shift register, LFSR) – rejestr przesuwający, którego bit wejściowy jest funkcją liniową jego poprzedniego stanu. Jedynymi funkcjami liniowymi w dziedzinie pojedynczych bitów są EX-OR oraz EX-NOR. Z tego powodu LFSR można zdefiniować jako rejestr przesuwający, którego wejście jest wysterowane funkcją XOR stanów kilku z komórek tworzących rejestr. Najczęstsze zastosowania LFSR to generowanie liczb pseudolosowych i pseudoszumu. Każdy LFSR jest związany z określonym wielomianem z pierścienia wielomianów gdzie jest ciałem skończonym Okres rejestru jest ograniczony przez stopień stowarzyszonego z nim wielomianu i wynosi maksymalnie gdzie jest stopniem wielomianu (ciało ma charakterystykę równą 2). Okres danego LFSR jest maksymalny jeżeli stowarzyszony z nim wielomian jest wielomianem pierwotnym. Rejestr taki, nazywamy rejestrem maksymalnej długości. Liczba wielomianów pierwotnych stopnia jest wyznaczona przez funkcję Eulera i wynosi Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie rejestrów maksymalnej długości. Jeżeli znany jest stopień wielomianu wystarczy zaledwie bitów wyjścia rejestru, by znaleźć ów wielomian. (Gdyż należy rozwiązać równań, każde z niewiadomymi, ale żeby otrzymać równań wystarczy zaledwie bitów wyjścia) W celu stosowania rejestrów w kryptografii, np. w szyfrach strumieniowych wykorzystuje się różne metody przełamywania liniowości:
* nieliniowa kombinacja kilku bitów z aktualnego stanu rejestru,
* kombinacja bitów z kilku różnych rejestrów za pomocą funkcji nieliniowej,
* nieliniowa kombinacja bitów z kilku różnych rejestrów (np. generator redukujący),
* regulacja większościowa częstotliwości taktowania rejestru (np. taka jak w szyfrze strumieniowym A5/1). (pl)
- Регистр сдвига с линейной обратной связью (РСЛОС, англ. linear feedback shift register, LFSR) — регистр битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии. По похожему принципу работают регистр сдвига с обратной связью по переносу и регистр сдвига с обобщённой обратной связью. (ru)
- Регістр зсуву з лінійним зворотним зв'язком (англ. linear feedback shift register, LFSR) — поширений спосіб отримання псевдовипадкових послідовностей, наприклад ключ-потоків. Це зумовлене такими причинами:
* LFSR добре втілюються на апаратному рівні;
* вони можуть утворювати послідовності із великими періодами;
* вони можуть утворювати послідовності з хорошими статистичними властивостями; і
* завдяки своїй будові, вони легко піддаються аналізу за допомогою алгебраїчних технік. (uk)
- 线性反馈移位寄存器（英語：Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。 赋给寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式，线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。 线性反馈移位寄存器的应用包括生成伪随机数，序列，快速数字计数器，还有。线性反馈移位寄存器在硬件和软件方面的应用都非常得普遍。 循环冗余校验中用于快速校验传输错误的数学原理，就与线性反馈移位寄存器密切相关。 (zh)
|
| rdfs:comment
|
- 선형 되먹임 시프트 레지스터(Linear feedback shift register, LFSR)는 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되는 구조를 가지고 있다. 이때 사용되는 선형 함수는 주로 배타적 논리합(XOR)이다. LFSR의 초기 비트 값은 시드(seed)라고 부른다. LFSR의 동작은 결정론적이기 때문에, LFSR로 생성되는 값의 수열은 그 이전 값에 의해 결정된다. 또한, 레지스터가 가질 수 있는 값의 개수는 유한하기 때문에, 이 수열은 특정한 주기에 의해 반복된다. 하지만 선형 함수를 잘 선택한다면 주기가 길고 무작위적으로 보이는 수열을 생성할 수 있다. LFSR는 의사 난수, (PRN), 빠른 디지털 카운터, 백지화 수열 등의 분야에서 사용된다. (ko)
- 線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、英: linear feedback shift register, LFSR）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。 値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。 LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。 LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。 (ja)
- Een linear feedback shift register, afgekort LFSR, is een schuifregister dat als belangrijkste kenmerk heeft dat bepaalde uitgangen via een xor-bewerking teruggekoppeld worden naar de ingang van het schuifregister. Het schuifregister is op deze manier in staat een rij bits te genereren. De lengte van de gegenereerde rij hangt af van welke uitgangen teruggekoppeld zijn, en is maximaal , met de lengte van het schuifregister (een ), of als met extra logica nul gedetecteerd wordt. Een belangrijk kenmerk van de rij is dat elk getal maar één keer voorkomt. De bits in het schuifregister worden in ieder geval vanaf een bepaalde combinatie cyclisch doorlopen. (nl)
- Регистр сдвига с линейной обратной связью (РСЛОС, англ. linear feedback shift register, LFSR) — регистр битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии. По похожему принципу работают регистр сдвига с обратной связью по переносу и регистр сдвига с обобщённой обратной связью. (ru)
- Регістр зсуву з лінійним зворотним зв'язком (англ. linear feedback shift register, LFSR) — поширений спосіб отримання псевдовипадкових послідовностей, наприклад ключ-потоків. Це зумовлене такими причинами:
* LFSR добре втілюються на апаратному рівні;
* вони можуть утворювати послідовності із великими періодами;
* вони можуть утворювати послідовності з хорошими статистичними властивостями; і
* завдяки своїй будові, вони легко піддаються аналізу за допомогою алгебраїчних технік. (uk)
- 线性反馈移位寄存器（英語：Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。 赋给寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式，线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。 线性反馈移位寄存器的应用包括生成伪随机数，序列，快速数字计数器，还有。线性反馈移位寄存器在硬件和软件方面的应用都非常得普遍。 循环冗余校验中用于快速校验传输错误的数学原理，就与线性反馈移位寄存器密切相关。 (zh)
- LFSR significa linear feedback shift register, que es tradueix com: registre de desplaçament amb retroalimentació lineal. És un registre de desplaçament en el qual l'entrada és un bit provinent d'aplicar una funció de transformació lineal a un estat anterior. (ca)
- Posuvný registr s lineární zpětnou vazbou (anglicky linear-feedback shift register, zkratkou LFSR) je posuvný registr, jehož výstup je lineárně závislý na jeho předchozích výstupech a stavu. Posuvné registry s lineární zpětnou vazbou jsou oblíbené jako generátory pseudonáhodných čísel a také v kryptografii jako součásti proudových šifer. Jejich výstup je kromě zpětnovazební funkce závislý také na jejich počátečním stavu, který se v případě použití jako generátorů pseudonáhodných čísel nazývá semínko (v případě šifrového použití je odvozený z klíče). (cs)
- Ein linear rückgekoppeltes Schieberegister (engl. linear feedback shift register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, das zur Erzeugung von streng deterministischen Pseudozufallszahlenfolgen eingesetzt werden kann. Zur Rückkopplung wird die lineare logische Funktion XOR verwendet. (de)
- LFSR significa linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior. (es)
- 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. 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. (en)
- Un registre à décalage à rétroaction linéaire, ou LFSR (sigle de l'anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite de bits qui peut être vue comme une suite récurrente linéaire sur le corps fini F2 à 2 éléments (0 et 1). La notion a été généralisée à n'importe quel corps fini. L’étendue des applications est très large : chiffrement des communications, contrôle d'erreurs sur la transmission de données, auto-test des composants électroniques… (fr)
- Il registro a scorrimento a retroazione lineare (linear feedback shift register, LFSR) è una tipologia di registri di traslazione i cui dati in ingresso sono prodotti da una funzione lineare dello stato interno. Le uniche funzioni lineari di singoli bit sono lo XOR e lo XNOR (xor inverso); perciò è un registro di traslazione i cui bit in ingresso sono prodotti dall'or esclusivo (xor) di alcuni bit memorizzati all'interno dei registri. (it)
- Rejestr przesuwający z liniowym sprzężeniem zwrotnym (ang. linear feedback shift register, LFSR) – rejestr przesuwający, którego bit wejściowy jest funkcją liniową jego poprzedniego stanu. Jedynymi funkcjami liniowymi w dziedzinie pojedynczych bitów są EX-OR oraz EX-NOR. Z tego powodu LFSR można zdefiniować jako rejestr przesuwający, którego wejście jest wysterowane funkcją XOR stanów kilku z komórek tworzących rejestr. Najczęstsze zastosowania LFSR to generowanie liczb pseudolosowych i pseudoszumu. (pl)
|
