ในทางคอมพิวเตอร์รีจิสเตอร์เลื่อนป้อนกลับเชิงเส้น ( LFSR ) คือรีจิสเตอร์เลื่อนที่มีบิตอินพุตเป็นฟังก์ชันเชิงเส้นของสถานะก่อนหน้า

ฟังก์ชันเชิงเส้นที่ใช้กันทั่วไปที่สุดสำหรับบิตเดี่ยวคือการดำเนินการเอกซ์คลูซีฟออร์ (XOR) ดังนั้น LFSR จึงมักเป็นรีจิสเตอร์เลื่อนที่มีบิตอินพุตถูกขับเคลื่อนด้วยการดำเนินการ XOR ของบิตบางส่วนจากค่ารีจิสเตอร์เลื่อนโดยรวม

ค่าเริ่มต้นของ LFSR เรียกว่า seed และเนื่องจากการทำงานของรีจิสเตอร์เป็นแบบกำหนดได้ ลำดับของค่าที่สร้างโดยรีจิสเตอร์จึงถูกกำหนดโดยสถานะปัจจุบัน (หรือสถานะก่อนหน้า) อย่างสมบูรณ์ ในทำนองเดียวกัน เนื่องจากรีจิสเตอร์มีสถานะที่เป็นไปได้จำนวนจำกัด มันจึงต้องเข้าสู่รอบการทำงานซ้ำในที่สุด อย่างไรก็ตาม LFSR ที่มีฟังก์ชันป้อนกลับที่เลือกอย่างเหมาะสมสามารถสร้างลำดับของบิตที่ดูเหมือนสุ่มและมีรอบการทำงานที่ยาวมากได้

การประยุกต์ใช้ LFSR ได้แก่ การสร้างตัวเลขสุ่มเทียมลำดับสัญญาณรบกวนเทียมตัวนับดิจิทัลความเร็วสูง และลำดับการปรับค่าสีขาวการใช้งาน LFSR ทั้งในรูปแบบฮาร์ดแวร์และซอฟต์แวร์นั้นพบได้ทั่วไป

คณิตศาสตร์ของการตรวจสอบความซ้ำซ้อนแบบวนรอบซึ่งใช้ในการตรวจสอบข้อผิดพลาดในการส่งอย่างรวดเร็ว มีความเกี่ยวข้องอย่างใกล้ชิดกับคณิตศาสตร์ของ LFSR ^{[ 1 ]}โดยทั่วไป เลขคณิตเบื้องหลัง LFSR ทำให้ LFSR มีความสง่างามมากในฐานะวัตถุที่จะศึกษาและนำไปใช้งาน เราสามารถสร้างตรรกะที่ค่อนข้างซับซ้อนได้ด้วยส่วนประกอบพื้นฐานที่เรียบง่าย อย่างไรก็ตาม ควรพิจารณาวิธีการอื่นๆ ที่มีความสง่างามน้อยกว่าแต่มีประสิทธิภาพดีกว่าด้วย

ตำแหน่งบิตที่มีผลต่อสถานะถัดไปเรียกว่าแทป (tap ) ในแผนภาพ แทปคือ [16,14,13,11] บิตขวาสุดของ LFSR เรียกว่า บิตเอาต์พุต (output bit) ซึ่งเป็นแทปเสมอ เพื่อให้ได้สถานะถัดไป บิตแทปจะถูก XOR ตามลำดับ จากนั้น บิตทั้งหมดจะถูกเลื่อนไปทางขวาหนึ่งตำแหน่ง โดยบิตขวาสุดจะถูกทิ้ง และผลลัพธ์ของการ XOR บิตแทปจะถูกป้อนกลับเข้าไปในบิตซ้ายสุดที่ว่างอยู่ เพื่อให้ได้กระแสเอาต์พุตแบบสุ่มเทียม ให้อ่านบิตขวาสุดหลังจากการเปลี่ยนสถานะแต่ละครั้ง

• LFSR ที่มีความยาวสูงสุดจะสร้างลำดับ m (กล่าวคือ มันจะวนรอบสถานะที่เป็นไปได้ทั้งหมด 2 ^m  − 1 สถานะภายในรีจิสเตอร์เลื่อน ยกเว้นสถานะที่บิตทั้งหมดเป็นศูนย์) เว้นแต่ว่ามันจะประกอบด้วยบิตศูนย์ทั้งหมด ซึ่งในกรณีนั้นมันจะไม่เปลี่ยนแปลงเลย
• นอกจากการป้อนกลับแบบ XOR ใน LFSR แล้ว ยังสามารถใช้XNOR ได้อีก ด้วย^{[ 2 ]}ฟังก์ชันนี้เป็นแผนที่เชิงเส้นไม่ใช่แผนที่เชิงเส้น อย่างแท้จริง แต่ส่งผลให้ได้ตัวนับพหุนามที่เทียบเท่ากัน ซึ่งสถานะเป็นส่วนเติมเต็มของสถานะของ LFSR สถานะที่มีค่าเป็นหนึ่งทั้งหมดถือว่าผิดกฎหมายเมื่อใช้การป้อนกลับแบบ XNOR เช่นเดียวกับสถานะที่มีค่าเป็นศูนย์ทั้งหมดถือว่าผิดกฎหมายเมื่อใช้ XOR สถานะนี้ถือว่าผิดกฎหมายเพราะตัวนับจะยังคง "ล็อก" อยู่ในสถานะนี้ วิธีนี้อาจเป็นประโยชน์ใน LFSR ฮาร์ดแวร์ที่ใช้ฟลิปฟลอปที่เริ่มต้นในสถานะศูนย์ เนื่องจากไม่ได้เริ่มต้นในสถานะล็อก ซึ่งหมายความว่ารีจิสเตอร์ไม่จำเป็นต้องกำหนดค่าเริ่มต้นก่อนเริ่มการทำงาน

ลำดับตัวเลขที่สร้างขึ้นโดย LFSR หรือ XNOR ที่เทียบเท่ากันนั้น สามารถถือได้ว่าเป็นระบบเลขฐานสองที่มีความถูกต้องเช่นเดียวกับรหัสเกรย์หรือรหัสเลขฐานสองแบบธรรมชาติ

การจัดเรียงแท็ปสำหรับการป้อนกลับใน LFSR สามารถแสดงได้ด้วยเลขคณิตฟิลด์จำกัดในรูปพหุนามมอด 2 ซึ่งหมายความว่าสัมประสิทธิ์ของพหุนามต้องเป็น 1 หรือ 0 เท่านั้น นี่เรียกว่าพหุนามป้อนกลับหรือพหุนามลักษณะเฉพาะส่วนกลับ ตัวอย่างเช่น ถ้าแท็ปอยู่ที่บิตที่ 16, 14, 13 และ 11 (ดังแสดงในภาพ) พหุนามป้อนกลับจะเป็นดังนี้

${\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1.}$

เลข "หนึ่ง" ในพหุนามไม่ได้หมายถึงแท็ป แต่หมายถึงอินพุตของบิตแรก (เช่นx ⁰ซึ่งเทียบเท่ากับ 1) กำลังของพจน์ต่างๆ แทนบิตที่ต่อแท็ป โดยนับจากซ้าย บิตแรกและบิตสุดท้ายจะเชื่อมต่อเป็นแท็ปอินพุตและเอาต์พุตตามลำดับเสมอ

LFSR มีความยาวสูงสุดก็ต่อเมื่อพหุนามป้อนกลับที่สอดคล้องกันเป็นพหุนามดั้งเดิมเหนือฟิลด์กาโลอิส GF(2) ^{[ 3 ] [ 4 ]}ซึ่งหมายความว่าเงื่อนไขต่อไปนี้เป็นเงื่อนไขที่จำเป็น (แต่ไม่เพียงพอ):

• จำนวนการแตะเป็นเลขคู่
• ชุดของจุดต่อ (tap) ต้องเป็นจำนวนเฉพาะสัมพัทธ์กัน กล่าวคือ จะต้องไม่มีตัวหารอื่นใดนอกจาก 1 ที่เป็นจุดต่อร่วมของทุกจุด

ตารางพหุนามดั้งเดิมที่สามารถใช้สร้าง LFSR ที่มีความยาวสูงสุดได้นั้นแสดงไว้ด้านล่างและในเอกสารอ้างอิง

สำหรับความยาว LFSR ที่กำหนด อาจมีลำดับแท็ปที่มีความยาวสูงสุดได้มากกว่าหนึ่งลำดับ นอกจากนี้ เมื่อพบลำดับแท็ปที่มีความยาวสูงสุดแล้ว ลำดับอื่นก็จะตามมาโดยอัตโนมัติ หากลำดับแท็ปใน LFSR nบิตคือ[ n , A , B , C , 0]โดยที่ 0 สอดคล้องกับ เทอม x ⁰  = 1 แล้ว ลำดับ "สะท้อน" ที่สอดคล้องกันคือ[ n , n − C , n − B , n − A , 0]ดังนั้น ลำดับแท็ป[32, 22, 2, 1, 0]จึงมีลำดับที่ตรงกันข้ามคือ[32, 31, 30, 10, 0]ทั้งสองให้ลำดับที่มีความยาวสูงสุด

ตัวอย่างในภาษาซีมีดังต่อไปนี้:

#include <stdint.h> unsigned lfsr_fib ( void ) { uint16_t start_state = 0xACE1u ; /* ค่า start state ใดๆ ที่ไม่ใช่ศูนย์ก็ใช้ได้ */ uint16_t lfsr = start_state ; uint16_t bit ; /* ต้องเป็น 16 บิตเพื่อให้สามารถใช้ bit<<15 ในภายหลังในโค้ดได้ */ unsigned period = 0 ;do { /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ bit = (( lfsr >> 0 ) ^ ( lfsr >> 2 ) ^ ( lfsr >> 3 ) ^ ( lfsr >> 5 )) & 1u ; lfsr = ( lfsr >> 1 ) | ( bit << 15 ); ++ period ; } while ( lfsr != start_state );ระยะเวลาการคืนสินค้า; }

หาก มีการดำเนินการตรวจสอบ ความเท่าเทียมกันหรือนับจำนวนข้อมูล อย่างรวดเร็ว บิตป้อนกลับสามารถคำนวณได้อย่างมีประสิทธิภาพมากขึ้นโดยใช้ผลคูณดอทของรีจิสเตอร์กับพหุนามลักษณะเฉพาะ:

• bit=parity(lfsr&0x002Du);หรือเทียบเท่า
• bit=popcnt(lfsr&0x002Du)/* & 1u */;(การดำเนินการนี้& 1uจะเปลี่ยน popcnt ให้เป็นฟังก์ชันพาริตีที่แท้จริง แต่การเลื่อนบิตในภายหลังbit << 15จะทำให้บิตที่สูงกว่าไม่มีความสำคัญ)

หากมีการดำเนินการหมุน สถานะใหม่สามารถคำนวณได้ดังนี้

• lfsr=rotateright((lfsr&~1u)|(bit&1u),1);หรือเทียบเท่า
• lfsr=rotateright(((bit^lfsr)&1u)^lfsr,1);

การกำหนดค่า LFSR นี้เรียกอีกอย่างว่าเกต XOR มาตรฐานแบบหลายต่อหนึ่งหรือ แบบภายนอก การกำหนดค่า Galois ทางเลือกจะอธิบายในส่วนถัดไป

ตัวอย่างการใช้งาน LFSR แบบ Fibonacci ที่คล้ายกัน (แท็ป 16 บิตที่ [16,15,13,4]) ในภาษา Python จะเป็นดังนี้

start_state = 1 << 15 | 1 lfsr = start_state period = 0ในขณะที่True : # taps: 16 15 13 4; พหุนามป้อนกลับ: x^16 + x^15 + x^13 + x^4 + 1 bit = ( lfsr ^ ( lfsr >> 1 ) ^ ( lfsr >> 3 ) ^ ( lfsr >> 12 )) & 1 lfsr = ( lfsr >> 1 ) | ( bit << 15 ) period += 1 ถ้าlfsr == start_state : พิมพ์( period ) หยุด

โดยใช้รีจิสเตอร์ขนาด 16 บิต และตัวแยกสัญญาณ XOR ที่บิตที่ 4, 13, 15 และ 16 จะกำหนดความยาวลำดับสูงสุด

LFSR ในรูปแบบ Galois ซึ่งตั้งชื่อตามนักคณิตศาสตร์ชาวฝรั่งเศสÉvariste Galois หรือที่รู้จักกันในชื่อ modular , internal XORsหรือone-to-many LFSRเป็นโครงสร้างทางเลือกที่สามารถสร้างกระแสเอาต์พุตเดียวกันกับ LFSR ทั่วไป (แต่มีการชดเชยเวลา) ^{[ 5 ]}ในรูปแบบ Galois เมื่อระบบได้รับสัญญาณนาฬิกา บิตที่ไม่ใช่ taps จะถูกเลื่อนไปทางขวาหนึ่งตำแหน่งโดยไม่เปลี่ยนแปลง ในทางกลับกัน taps จะถูก XOR กับบิตเอาต์พุตก่อนที่จะถูกจัดเก็บในตำแหน่งถัดไป บิตเอาต์พุตใหม่จะเป็นบิตอินพุตถัดไป ผลของสิ่งนี้คือ เมื่อบิตเอาต์พุตเป็นศูนย์ บิตทั้งหมดในรีจิสเตอร์จะเลื่อนไปทางขวาโดยไม่เปลี่ยนแปลง และบิตอินพุตจะกลายเป็นศูนย์ เมื่อบิตเอาต์พุตเป็น 1 บิตในตำแหน่งแท็ปทั้งหมดจะเปลี่ยนค่า (ถ้าเป็น 0 จะกลายเป็น 1 และถ้าเป็น 1 จะกลายเป็น 0) จากนั้นรีจิสเตอร์ทั้งหมดจะถูกเลื่อนไปทางขวา และบิตอินพุตจะกลายเป็น 1

เพื่อให้ได้กระแสเอาต์พุตเดียวกัน ลำดับของแท็ปจะต้องเป็นลำดับตรงกันข้าม (ดูด้านบน) กับลำดับของ LFSR แบบดั้งเดิม มิฉะนั้นกระแสจะกลับทิศทาง โปรดทราบว่าสถานะภายในของ LFSR ไม่จำเป็นต้องเหมือนกันเสมอไป รีจิสเตอร์กาโลอิสที่แสดงมีกระแสเอาต์พุตเดียวกันกับรีจิสเตอร์ฟิโบนาชชีในส่วนแรก มีการชดเชยเวลาอยู่ระหว่างกระแส ดังนั้นจึงจำเป็นต้องใช้จุดเริ่มต้นที่แตกต่างกันเพื่อให้ได้เอาต์พุตเดียวกันในแต่ละรอบ

• Galois LFSR ไม่ได้นำทุกแท็ปมาต่อกันเพื่อสร้างอินพุตใหม่ (การดำเนินการ XOR เกิดขึ้นภายใน LFSR และไม่มีเกต XOR ใดทำงานแบบอนุกรม ดังนั้นเวลาในการแพร่กระจายจึงลดลงเหลือเพียงเวลาของการดำเนินการ XOR เพียงครั้งเดียว แทนที่จะเป็นทั้งสายโซ่) ด้วยเหตุนี้จึงสามารถคำนวณแต่ละแท็ปแบบขนานได้ ซึ่งจะเพิ่มความเร็วในการประมวลผล
• ในการนำ LFSR ไปใช้ในซอฟต์แวร์ รูปแบบ Galois มีประสิทธิภาพมากกว่า เนื่องจากสามารถดำเนินการ XOR ทีละคำได้ โดยจะต้องตรวจสอบเฉพาะบิตเอาต์พุตทีละบิตเท่านั้น

ด้านล่างนี้คือ ตัวอย่างโค้ดภาษา Cสำหรับตัวอย่าง Galois LFSR ที่มีคาบสูงสุด 16 บิตตามที่แสดงในรูป:

#include <stdint.h> unsigned lfsr_galois ( void ) { uint16_t start_state = 0xACE1u ; /* ค่า start state ใดๆ ที่ไม่ใช่ศูนย์ก็ใช้ได้ */ uint16_t lfsr = start_state ; unsigned period = 0 ;do { #ifndef LEFT unsigned lsb = lfsr & 1u ; /* รับค่า LSB (เช่น บิตเอาต์พุต) */ lfsr >>= 1 ; /* รีจิสเตอร์เลื่อน */ if ( lsb ) /* ถ้าบิตเอาต์พุตเป็น 1 */ lfsr ^= 0xB400u ; /* ใช้มาสก์สลับ */ #else unsigned msb = ( int16_t ) lfsr < 0 ; /* รับค่า MSB (เช่น บิตเอาต์พุต) */ lfsr <<= 1 ; /* รีจิสเตอร์เลื่อน */ if ( msb ) /* ถ้าบิตเอาต์พุตเป็น 1 */ lfsr ^= 0x002Du ; /* ใช้มาสก์สลับ */ #endif ++ period ; } while ( lfsr != start_state );ระยะเวลาการคืนสินค้า; }

นอกจากนี้ ยังสามารถเขียนเงื่อนไข ได้ในรูปแบบ ที่อาจทำให้โค้ดมีประสิทธิภาพมากขึ้นในคอมไพเลอร์บางตัว ยิ่งไปกว่านั้น รูปแบบการเลื่อนบิตไปทางซ้ายอาจทำให้โค้ดดียิ่งขึ้นไปอีก เนื่องจากบิต ที่มีค่าสูงสุด (msb)คือค่าทดจากการบวกเข้ากับตัวมันเอง if(lsb)lfsr^=0xB400u;lfsr^=(-lsb)&0xB400u;lfsr

สถานะและบิตที่ได้สามารถนำมาผสมผสานและคำนวณแบบขนานได้เช่นกัน ฟังก์ชันต่อไปนี้คำนวณ 64 บิตถัดไปโดยใช้พหุนาม 63 บิต: ${\displaystyle x^{63}+x^{62}+1}$

#include <stdint.h>uint64_t prsg63 ( uint64_t lfsr ) { lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; return lfsr ; }

LFSR แบบไบนารี Galois ดังที่แสดงข้างต้น สามารถขยายให้ครอบคลุม ตัวอักษร q -ary ใดๆ ก็ได้ {0, 1, ..., q  − 1} (เช่น สำหรับไบนารีq = 2 และตัวอักษรก็คือ {0, 1}) ในกรณีนี้ ส่วนประกอบ Exclusive-OR จะถูกขยายเป็นการบวกโมดูลัส-q (โปรดทราบว่า XOR คือการบวกโมดูลัส 2) และบิตป้อนกลับ (บิตเอาต์พุต) จะถูกคูณ (โมดูลัส -q ) ด้วย ค่า q -ary ซึ่งเป็นค่าคงที่สำหรับแต่ละจุดแตะเฉพาะ โปรดทราบว่านี่เป็นการขยายกรณีไบนารีเช่นกัน โดยที่การป้อนกลับจะถูกคูณด้วย 0 (ไม่มีการป้อนกลับ กล่าวคือ ไม่มีจุดแตะ) หรือ 1 (มีการป้อนกลับ) เมื่อกำหนดค่าจุดแตะที่เหมาะสมแล้ว LFSR ดังกล่าวสามารถใช้สร้างฟิลด์ Galoisสำหรับค่าเฉพาะq ใดๆ ก็ได้

ดังที่George Marsaglia ^{[ 6 ]} ได้แสดงไว้ และRichard P. Brent [ ^{7 ] ได้} วิเคราะห์เพิ่มเติม ว่ารีจิสเตอร์เลื่อนป้อนกลับเชิงเส้นสามารถนำไปใช้โดยใช้การดำเนินการ XOR และ Shift ได้ แนวทางนี้เอื้อต่อการดำเนินการที่รวดเร็วในซอฟต์แวร์ เนื่องจากการดำเนินการเหล่านี้มักจะแมปได้อย่างมีประสิทธิภาพกับคำสั่งโปรเซสเซอร์สมัยใหม่

ด้านล่างนี้คือ ตัวอย่างโค้ด Cสำหรับ LFSR Xorshift ที่มีคาบสูงสุด 16 บิต โดยใช้ชุดตัวเลข 7,9,13 จาก John Metcalf: ^{[ 8 ]}

#include <stdint.h> unsigned lfsr_xorshift ( void ) { uint16_t start_state = 0xACE1u ; /* ค่า start state ใดๆ ที่ไม่ใช่ศูนย์ก็ใช้ได้ */ uint16_t lfsr = start_state ; unsigned period = 0 ;do { // ชุดตัวเลข 7, 9, 13 จาก http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html lfsr ^= lfsr >> 7 ; lfsr ^= lfsr << 9 ; lfsr ^= lfsr >> 13 ; ++ period ; } while ( lfsr != start_state );ระยะเวลาการคืนสินค้า; }

LFSR แบบไบนารีของทั้งการกำหนดค่าฟิโบนาชชีและกาโลอิสสามารถแสดงเป็นฟังก์ชันเชิงเส้นโดยใช้เมทริกซ์ใน(ดูGF(2) ) ^{[ 9 ]}โดยใช้เมทริกซ์คู่ของพหุนามลักษณะเฉพาะของ LFSR และกำหนดเมล็ดพันธุ์เป็นเวกเตอร์คอลัมน์สถานะของรีจิสเตอร์ในการกำหนดค่าฟิโบนาชชีหลังจากขั้นตอนจะได้รับโดย ${\displaystyle \mathbb {F} _{2}}$${\displaystyle (a_{0},a_{1},\dots ,a_{n-1})^{\mathrm {T} }}$${\displaystyle k}$

${\displaystyle {\begin{pmatrix}a_{k}\\a_{k+1}\\a_{k+2}\\\vdots \\a_{k+n-1}\end{pmatrix}}={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}{\begin{pmatrix}a_{k-1}\\a_{k}\\a_{k+1}\\\vdots \\a_{k+n-2}\end{pmatrix}}={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}^{k}{\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\\\vdots \\a_{n-1}\end{pmatrix}}}$

เมทริกซ์สำหรับรูปแบบกาโลอิสที่สอดคล้องกันคือ:

${\displaystyle {\begin{pmatrix}c_{n-1}&1&0&\cdots &0\\c_{n-2}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{1}&0&\cdots &0&1\\c_{0}&0&\cdots &\cdots &0\end{pmatrix}}}$

เพื่อการเริ่มต้นที่เหมาะสม

${\displaystyle a'_{i}=\sum _{j=0}^{i}a_{i-j}c_{i},\ 0\leq i<n}$

สัมประสิทธิ์ตัวบนสุดของเวกเตอร์คอลัมน์ :

${\displaystyle {\begin{pmatrix}c_{n-1}&1&0&\cdots &0\\c_{n-2}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{1}&0&\cdots &0&1\\c_{0}&0&\cdots &\cdots &0\end{pmatrix}}^{k}{\begin{pmatrix}a'_{0}\\a'_{1}\\a'_{2}\\\vdots \\a'_{n-1}\end{pmatrix}}}$

ให้พจน์a _kของลำดับเดิม

รูปแบบเหล่านี้สามารถขยายไปสู่สาขาใดๆ ก็ได้โดยธรรมชาติ

ตารางต่อไปนี้แสดงรายการตัวอย่างของพหุนามป้อนกลับความยาวสูงสุด ( พหุนามดั้งเดิม ) สำหรับความยาวรีจิสเตอร์เลื่อนสูงสุด 24 รูปแบบสำหรับ LFSR ความยาวสูงสุดได้รับการพัฒนาโดยSolomon W. Golombในหนังสือของเขาในปี 1967 ^{[ 10 ]}จำนวนพหุนามดั้งเดิม ที่แตกต่างกัน จะเพิ่มขึ้นแบบเลขชี้กำลังตามความยาวรีจิสเตอร์เลื่อนและสามารถคำนวณได้อย่างแม่นยำโดยใช้ฟังก์ชันโทเทียนต์ของออยเลอร์^{[ 11 ]} (ลำดับA011260ในOEIS )

บิต (น)	พหุนามป้อนกลับ	ก๊อกน้ำ	ก๊อก ( เลขฐานสิบหก )	ระยะเวลา ( ) ${\displaystyle 2^{n}-1}$
2	${\displaystyle x^{2}+x+1}$	11	0x3	3
3	${\displaystyle x^{3}+x^{2}+1}$	110	0x6	7
4	${\displaystyle x^{4}+x^{3}+1}$	1100	0xC	15
5	${\displaystyle x^{5}+x^{3}+1}$	10100	0x14	31
6	${\displaystyle x^{6}+x^{5}+1}$	110000	0x30	63
7	${\displaystyle x^{7}+x^{6}+1}$	1,100,000 บาท	0x60	127
8	${\displaystyle x^{8}+x^{6}+x^{5}+x^{4}+1}$	10111000	0xB8	255
9	${\displaystyle x^{9}+x^{5}+1}$	100010000	0x110	511
10	${\displaystyle x^{10}+x^{7}+1}$	1001000000	0x240	1,023
11	${\displaystyle x^{11}+x^{9}+1}$	10100000000	0x500	2,047
12	${\displaystyle x^{12}+x^{11}+x^{10}+x^{4}+1}$	111000001000	0xE08	4,095
13	${\displaystyle x^{13}+x^{12}+x^{11}+x^{8}+1}$	1110010000000	0x1C80	8,191
14	${\displaystyle x^{14}+x^{13}+x^{12}+x^{2}+1}$	11100000000010	0x3802	16,383
15	${\displaystyle x^{15}+x^{14}+1}$	110000000000000	0x6000	32,767
16	${\displaystyle x^{16}+x^{15}+x^{13}+x^{4}+1}$	1101000000001000	0xD008	65,535
17	${\displaystyle x^{17}+x^{14}+1}$	10010000000000000	0x12000	131,071
18	${\displaystyle x^{18}+x^{11}+1}$	100000010000000000	0x20400	262,143
19	${\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}$	1110010000000000000	0x72000	524,287
20	${\displaystyle x^{20}+x^{17}+1}$	10010000000000000000	0x90000	1,048,575
21	${\displaystyle x^{21}+x^{19}+1}$	101000000000000000000	0x140000	2,097,151
22	${\displaystyle x^{22}+x^{21}+1}$	1100000000000000000000	0x300000	4,194,303
23	${\displaystyle x^{23}+x^{18}+1}$	10000100000000000000000	0x420000	8,388,607
24	${\displaystyle x^{24}+x^{23}+x^{22}+x^{17}+1}$	111000010000000000000000	0xE10000	16,777,215

• เลข 1 และ 0 จะปรากฏเป็น "ชุด" เช่น สตรีมเอาต์พุต 1110010 ประกอบด้วยชุดสี่ชุดที่มีความยาว 3, 2, 1, 1 ตามลำดับ ในหนึ่งคาบของ LFSR สูงสุด จะมีชุดเกิดขึ้น 2n ^{− 1}ชุด (ในตัวอย่างข้างต้น LFSR 3 บิตมี 4 ชุด) ครึ่งหนึ่งของชุดเหล่านี้มีความยาวหนึ่งบิต หนึ่งในสี่มีความยาวสองบิต จนถึงชุดศูนย์หนึ่งชุดที่มีความยาวn  − 1 บิต และชุดหนึ่งหนึ่งชุดที่ มีความยาว nบิต การกระจายตัวนี้เกือบเท่ากับค่าคาดหวัง ทางสถิติ สำหรับลำดับสุ่มอย่างแท้จริง อย่างไรก็ตาม ความน่าจะเป็นที่จะพบการกระจายตัวนี้อย่างแม่นยำในตัวอย่างของลำดับสุ่มอย่างแท้จริงนั้นค่อนข้างต่ำ
• สตรีมเอาต์พุตของ LFSR เป็นแบบกำหนดได้หากทราบสถานะปัจจุบันและตำแหน่งของเกต XOR ใน LFSR ก็สามารถคาดการณ์สถานะถัดไปได้^{[ 12 ]}ซึ่งเป็นไปไม่ได้กับเหตุการณ์สุ่มอย่างแท้จริง สำหรับ LFSR ที่มีความยาวสูงสุด การคำนวณสถานะถัดไปจะง่ายกว่ามาก เนื่องจากมีจำนวนสถานะถัดไปที่จำกัดสำหรับแต่ละความยาว
• กระแสเอาต์พุตสามารถย้อนกลับได้ กล่าวคือ LFSR ที่มีแท็ปแบบมิเรอร์จะวนรอบลำดับเอาต์พุตในลำดับย้อนกลับ
• ค่าที่ประกอบด้วยเลขศูนย์ทั้งหมดไม่สามารถปรากฏได้ ดังนั้น LFSR ที่มีความยาวn จึง ไม่สามารถใช้สร้างค่า^{2n ทั้งหมดได้}

LFSR สามารถนำไปใช้ในฮาร์ดแวร์ได้ ซึ่งทำให้มีประโยชน์ในแอปพลิเคชันที่ต้องการการสร้างลำดับสุ่มเทียมอย่างรวดเร็ว เช่น วิทยุ สเปรดสเปกตรัมแบบลำดับตรงนอกจากนี้ LFSR ยังถูกใช้เพื่อสร้างสัญญาณรบกวนสีขาวโดยประมาณในเครื่องกำเนิดเสียงแบบโปรแกรม ได้ต่างๆ อีก ด้วย

ลำดับสถานะที่ซ้ำกันของ LFSR ช่วยให้สามารถใช้เป็นตัวแบ่งสัญญาณนาฬิกาหรือตัวนับได้เมื่อยอมรับลำดับที่ไม่ใช่ไบนารี ซึ่งมักเป็นกรณีที่ตำแหน่งดัชนีหรือเฟรมของคอมพิวเตอร์จำเป็นต้องอ่านได้ด้วยเครื่อง^{[ 12 ]}ตัวนับ LFSR มีตรรกะป้อนกลับที่ง่ายกว่าตัวนับไบนารีธรรมชาติหรือตัวนับรหัสเกรย์ดังนั้นจึงสามารถทำงานที่อัตราสัญญาณนาฬิกาที่สูงกว่าได้ อย่างไรก็ตาม จำเป็นต้องตรวจสอบให้แน่ใจว่า LFSR จะไม่เข้าสู่สถานะล็อกอัพ (ศูนย์ทั้งหมดสำหรับ LFSR ที่ใช้ XOR และหนึ่งทั้งหมดสำหรับ LFSR ที่ใช้ XNOR) ตัวอย่างเช่น โดยการตั้งค่าล่วงหน้าเมื่อเริ่มต้นให้เป็นสถานะอื่นใดในลำดับนั้น เป็นไปได้ที่จะนับขึ้นและลงด้วย LFSR นอกจากนี้ LFSR ยังถูกใช้เป็นตัวนับโปรแกรมสำหรับ CPUซึ่งต้องให้โปรแกรมนั้น "สุ่ม" และทำเพื่อประหยัดเกตเมื่อมีข้อจำกัด (ใช้เกตน้อยกว่าตัวบวก) และเพื่อความเร็ว (เนื่องจาก LFSR ไม่ต้องการโซ่ทดที่ยาว)

ตารางพหุนามดั้งเดิมแสดงให้เห็นว่า LFSR สามารถจัดเรียงในรูปแบบฟิโบนาชชีหรือกาโลอิสเพื่อให้ได้คาบสูงสุดได้อย่างไร เราสามารถได้คาบอื่นๆ โดยการเพิ่มตรรกะบางอย่างเข้าไปใน LFSR ที่มีคาบยาวกว่า ซึ่งจะทำให้ลำดับสั้นลงโดยการข้ามสถานะบางสถานะ

LFSR (Linear Flow System) ถูกนำมาใช้เป็น ตัวสร้างเลขสุ่มเทียม สำหรับใช้ในการเข้ารหัสแบบสตรีมมา นานแล้ว เนื่องจากสร้างได้ง่ายจาก วงจร ไฟฟ้าเชิงกลหรืออิเล็กทรอนิกส์ แบบง่ายๆ มี คาบเวลาที่ยาวนานและ สตรีมเอาต์พุต ที่กระจายตัวอย่าง สม่ำเสมอมาก อย่างไรก็ตาม LFSR เป็นระบบเชิงเส้น ทำให้ สามารถ ถอดรหัสได้ ค่อนข้างง่าย ตัวอย่างเช่น เมื่อทราบข้อความต้นฉบับและข้อความเข้ารหัสที่สอดคล้องกันผู้โจมตีสามารถดักจับและกู้คืนส่วนหนึ่งของสตรีมเอาต์พุตของ LFSR ที่ใช้ในระบบดังกล่าว และจากส่วนของสตรีมเอาต์พุตนั้น สามารถสร้าง LFSR ที่มีขนาดเล็กที่สุดที่จำลองผู้รับที่ตั้งใจไว้โดยใช้อัลกอริทึม Berlekamp-Masseyจากนั้นสามารถป้อนส่วนของสตรีมเอาต์พุตที่ดักจับได้เข้าไปใน LFSR นี้เพื่อกู้คืนข้อความต้นฉบับที่เหลืออยู่

โดยทั่วไปแล้ว มีวิธีการสามวิธีที่ใช้ในการลดปัญหาดังกล่าวในระบบเข้ารหัสแบบสตรีมที่ใช้ LFSR:

• การรวมกัน แบบไม่เชิงเส้นของบิตหลายบิต จาก สถานะ LFSR ;
• การรวมกันแบบไม่เชิงเส้นของบิตเอาต์พุตของ LFSR สองตัวขึ้นไป (ดูเพิ่มเติม: ตัวสร้างที่หดตัว ) หรือการใช้อัลกอริทึมวิวัฒนาการเพื่อแนะนำความไม่เชิงเส้น^{[ 13 ]}
• การกำหนดจังหวะการทำงานของ LFSR ที่ไม่สม่ำเสมอ เช่นเดียวกับใน วงจรสร้างสัญญาณขั้นบันได แบบสลับ

การเข้ารหัสแบบสตรีมที่ใช้ LFSR ที่สำคัญ ได้แก่A5/1และA5/2ซึ่งใช้ในโทรศัพท์มือถือGSM , E0ซึ่งใช้ในบลูทูธและตัวสร้างการย่อขนาดการเข้ารหัส A5/2 ถูกเจาะได้แล้ว และทั้ง A5/1 และ E0 ก็มีจุดอ่อนที่ร้ายแรง^{[ 14 ] [ 15 ]}

รีจิสเตอร์เลื่อนป้อนกลับเชิงเส้นมีความสัมพันธ์อย่างมากกับตัวสร้างเชิงเส้นที่สอดคล้องกัน^{[ 16 ]}

LFSR ถูกนำมาใช้ในการทดสอบวงจรเพื่อสร้างรูปแบบการทดสอบ (สำหรับการทดสอบแบบครบถ้วน การทดสอบแบบสุ่มเทียม หรือการทดสอบแบบเกือบครบถ้วน) และเพื่อการวิเคราะห์ลายเซ็น

LFSR แบบสมบูรณ์มักใช้เป็นตัวสร้างรูปแบบสำหรับการทดสอบแบบครอบคลุม เนื่องจากครอบคลุมอินพุตที่เป็นไปได้ทั้งหมดสำหรับ วงจรที่มีอินพุต nตัว LFSR ที่มีความยาวสูงสุดและ LFSR แบบถ่วงน้ำหนักใช้กันอย่างแพร่หลายเป็นตัวสร้างรูปแบบทดสอบแบบสุ่มเทียมสำหรับการใช้งานทดสอบแบบสุ่มเทียม

ใน เทคนิค การทดสอบตัวเองแบบในตัว (BIST) การจัดเก็บเอาต์พุตของวงจรทั้งหมดไว้ในชิปนั้นเป็นไปไม่ได้ แต่สามารถบีบอัดเอาต์พุตของวงจรเพื่อสร้างลายเซ็นที่จะนำไปเปรียบเทียบกับลายเซ็นมาตรฐาน (ของวงจรที่ดี) เพื่อตรวจจับข้อผิดพลาดได้ เนื่องจากการบีบอัดนี้มีการสูญเสียข้อมูล จึงมีความเป็นไปได้เสมอที่เอาต์พุตที่ผิดพลาดจะสร้างลายเซ็นเดียวกันกับลายเซ็นมาตรฐาน และไม่สามารถตรวจจับข้อผิดพลาดได้ สภาวะนี้เรียกว่าการบดบังข้อผิดพลาดหรือการปลอมแปลง BIST ทำได้โดยใช้รีจิสเตอร์ลายเซ็นแบบหลายอินพุต (MISR หรือ MSR) ซึ่งเป็นประเภทหนึ่งของ LFSR LFSR มาตรฐานมีเกต XOR หรือ XNOR เพียงตัวเดียว โดยอินพุตของเกตเชื่อมต่อกับ "แท็ป" หลายตัว และเอาต์พุตเชื่อมต่อกับอินพุตของฟลิปฟลอปตัวแรก MISR มีโครงสร้างเดียวกัน แต่ป้อนอินพุตไปยังฟลิปฟลอปแต่ละตัวผ่านเกต XOR/XNOR ตัวอย่างเช่น MISR 4 บิต มีเอาต์พุตแบบขนาน 4 บิต และอินพุตแบบขนาน 4 บิต อินพุตของฟลิปฟลอปตัวแรกจะถูก XOR/XNORd กับบิตอินพุตขนานศูนย์และ "แทป" อินพุตของฟลิปฟลอปตัวอื่นๆ จะถูก XOR/XNORd กับเอาต์พุตของฟลิปฟลอปตัวก่อนหน้าและบิตอินพุตขนานที่สอดคล้องกัน ดังนั้น สถานะถัดไปของ MISR จะขึ้นอยู่กับสถานะหลายสถานะล่าสุด แทนที่จะเป็นเพียงสถานะปัจจุบัน ด้วยเหตุนี้ MISR จะสร้างลายเซ็นทองคำเดียวกันเสมอ ตราบใดที่ลำดับอินพุตเหมือนกันทุกครั้ง แอปพลิเคชันล่าสุด^{[ 17 ]}เสนอให้ใช้ฟลิปฟลอปแบบเซ็ต-รีเซ็ตเป็น "แทป" ของ LFSR ซึ่งช่วยให้ระบบ BIST สามารถเพิ่มประสิทธิภาพการจัดเก็บ เนื่องจากฟลิปฟลอปแบบเซ็ต-รีเซ็ตสามารถบันทึกเมล็ดพันธุ์เริ่มต้นเพื่อสร้างกระแสบิตทั้งหมดจาก LFSR ได้ อย่างไรก็ตาม สิ่งนี้จำเป็นต้องมีการเปลี่ยนแปลงในสถาปัตยกรรมของ BIST ซึ่งเป็นทางเลือกสำหรับแอปพลิเคชันเฉพาะ

เพื่อป้องกันไม่ให้ลำดับซ้ำสั้นๆ (เช่น ลำดับของ 0 หรือ 1) ก่อให้เกิดเส้นสเปกตรัมที่อาจทำให้การติดตามสัญลักษณ์ที่ตัวรับซับซ้อนขึ้น หรือรบกวนการส่งสัญญาณอื่นๆ ลำดับบิตข้อมูลจะถูกรวมเข้ากับเอาต์พุตของรีจิสเตอร์ป้อนกลับเชิงเส้น (LFSR) ก่อนการมอดูเลชั่นและการส่งสัญญาณ การเข้ารหัสนี้จะถูกกำจัดออกที่ตัวรับหลังจากดีมอดูเลชั่น เมื่อ LFSR ทำงานที่อัตราบิต เดียวกัน กับกระแสสัญลักษณ์ที่ส่ง เทคนิคนี้เรียกว่าการเข้ารหัสแบบสุ่ม (scrambling ) เมื่อ LFSR ทำงานเร็วกว่ากระแสสัญลักษณ์อย่างมาก ลำดับบิตที่สร้างโดย LFSR เรียกว่ารหัสชิปปิ้ง (chipping code ) รหัสชิปปิ้งจะถูกรวมเข้ากับข้อมูลโดยใช้ การเลือก แบบเอกซ์คลูซีฟหรือ ( OR) ก่อนการส่งโดยใช้การเข้ารหัสแบบไบนารีเฟสชิฟต์คีย์ (BIN) หรือวิธีการมอดูเลชั่นที่คล้ายกัน สัญญาณที่ได้จะมีแบนด์วิดท์สูงกว่าข้อมูล ดังนั้นจึงเป็นวิธี การสื่อสาร แบบสเปรดสเปกตรัมเมื่อใช้เฉพาะคุณสมบัติสเปรดสเปกตรัม เทคนิคนี้เรียกว่าสเปรดสเปกตรัมลำดับตรง (direct-sequence spread spectrum ) เมื่อใช้เพื่อแยกแยะสัญญาณหลายสัญญาณที่ส่งในช่องสัญญาณเดียวกันในเวลาและความถี่เดียวกัน จะเรียกว่าการเข้าถึงหลายช่องสัญญาณแบบแบ่งรหัส (code-division multiple access )

ทั้งสองวิธีนี้ไม่ควรสับสนกับการเข้ารหัสหรือการถอดรหัสการสุ่มและการกระจายสัญญาณด้วย LFSR ไม่ได้ปกป้องข้อมูลจากการดักฟัง แต่เป็นการใช้เพื่อสร้างกระแสข้อมูลที่เทียบเท่ากัน ซึ่งมีคุณสมบัติทางวิศวกรรมที่เอื้ออำนวยต่อการปรับสัญญาณและการถอดรหัสสัญญาณอย่างมีประสิทธิภาพและแข็งแกร่ง

ระบบกระจายเสียงดิจิทัลที่ใช้รีจิสเตอร์ป้อนกลับเชิงเส้น:

• มาตรฐาน ATSC (ระบบส่งสัญญาณโทรทัศน์ดิจิทัล – อเมริกาเหนือ)
• DAB ( ระบบกระจายเสียงดิจิทัล – สำหรับวิทยุ)
• DVB-T (ระบบส่งสัญญาณโทรทัศน์ดิจิทัล – ยุโรป ออสเตรเลีย และบางส่วนของเอเชีย)
• NICAM (ระบบเสียงดิจิทัลสำหรับโทรทัศน์)

ระบบสื่อสารดิจิทัลอื่นๆ ที่ใช้ LFSRs:

• บริการธุรกิจของ Intelsat (IBS)
• อัตราการส่งข้อมูลระดับกลาง (IDR)
• บีบีซี 2.0
• SDI (การส่งสัญญาณผ่านอินเทอร์เฟซดิจิทัลแบบอนุกรม)
• การรับส่งข้อมูลผ่านเครือข่ายโทรศัพท์สาธารณะ (PSTN ) (ตามข้อแนะนำของITU-T V-series)
• ระบบโทรศัพท์มือถือ CDMA (Code Division Multiple Access)
• อีเธอร์เน็ต 100BASE-T2 "เร็ว"จะเข้ารหัสบิตโดยใช้ LFSR
• อีเธอร์เน็ต 1000BASE-Tซึ่งเป็นรูปแบบที่พบได้บ่อยที่สุดของกิกะบิตอีเธอร์เน็ต ใช้การเข้ารหัสบิตแบบ LFSR
• พีซีไอ เอ็กซ์เพรส
• SATA ^{[ 18 ]}
• ซีเรียล แอทแทคซี (SAS/SPL)
• ยูเอสบี 3.0
• มาตรฐาน IEEE 802.11aใช้ LFSR ในการเข้ารหัสบิต
• เลเยอร์การเชื่อมต่อ Bluetooth Low Energyใช้ LFSR (หรือที่เรียกว่าการทำให้ขาวขึ้น)
• ระบบนำทางด้วยดาวเทียมเช่นGPSและGLONASSระบบปัจจุบันทั้งหมดใช้เอาต์พุต LFSR เพื่อสร้างรหัสการวัดระยะบางส่วนหรือทั้งหมด (เช่น รหัสชิปปิ้งสำหรับ CDMA หรือ DSSS) หรือเพื่อปรับคลื่นพาหะโดยไม่มีข้อมูล (เช่น รหัสการวัดระยะ L2 CL ของ GPS) GLONASS ยังใช้การเข้าถึงแบบหลายผู้ใช้โดยแบ่งความถี่ร่วมกับ DSSS ด้วย

LFSR ยังถูกใช้ใน ระบบ รบกวนสัญญาณวิทยุเพื่อสร้างสัญญาณรบกวนแบบสุ่มเทียม เพื่อเพิ่มระดับสัญญาณรบกวนของระบบสื่อสารเป้าหมาย

สัญญาณเวลาของเยอรมันDCF77นอกเหนือจากการใช้การเข้ารหัสแอมพลิจูดแล้ว ยังใช้การเข้ารหัสแบบเปลี่ยนเฟสที่ขับเคลื่อนด้วย LFSR 9 ขั้นตอน เพื่อเพิ่มความแม่นยำของเวลาที่ได้รับและความทนทานของกระแสข้อมูลเมื่อมีสัญญาณรบกวน^{[ 19 ]}

• กังหันลม
• พายุทอร์นาโดเมอร์เซนน์
• ลำดับความยาวสูงสุด
• รีจิสเตอร์เลื่อนป้อนกลับแบบอนาล็อก
• NLFSR (Non-Linear Feedback Shift Register)
• ตัวนับวงแหวน
• ลำดับไบนารีแบบสุ่มเทียม
• ลำดับทองคำ
• ลำดับ JPL
• ลำดับคาซามิ
• อัลกอริทึมเบอร์เลแคมป์-แมสซีย์

• https://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf
• http://users.ece.cmu.edu/~koopman/lfsr/index.html — ตารางพหุนามป้อนกลับที่มีความยาวสูงสุดสำหรับ 2-64 บิต
• https://github.com/hayguen/mlpolygen — โค้ดสำหรับสร้างพหุนามป้อนกลับที่มีความยาวสูงสุด

• LFSR และการสร้างความสุ่มโดยธรรมชาติ: บันทึกจาก NKS