A truth-table, and symbol, for a two-input gate is show here.īecause of the way these gates are applied, if there is no tap, each bit is shifted along unchanged. It has many interesting uses in electronics and computer science (particularly as applying the XOR function twice in a row with the same value returns a number to its original state). The easiest way to think about it is with the phrase ”One or the other, but not both”. In this LFSR there are four taps: 16,14,13,11 (The tap at 16 does not need a gate as the other input is always zero as as result of the shift).Īn exclusive-OR gate (XOR), is a very common component in electronics. The other input to the gate is provided by the LSB of the input stream that will get shifted off the end with the operation. The bits that could change are called taps, and these taps provide one input into a two-input XOR gate. Some bits are shifted, unchanged however, some bits potentially change by the application of XOR operations. The basic premise of the LFSR is that all the bits of the input are shifted right one position. The diagram below shows a binary representation of a 16-bit Galois LFSR. The particular kind of LFSR I’m going to model today is called a Galois LFSR, named after the French mathematician Évariste Galois (who tragically perished after being shot in a duel at the young age of just 20). They have lots of cool uses, but first let’s take a look at how they work. They are deterministic the same input will always give the same output. This article is about Linear Feedback Shift Registers, commonly referred to as LFSRs.Īn LFSR is like a black box into which you feed a number, and the generated output is some linear function of the input (typically created by some combination of shifting, and Exclusive-OR, of the bits).
0 kommentar(er)
