รหัสวงจรมีลักษณะเฉพาะโดยข้อเท็จจริงที่ว่าในระหว่างการเปลี่ยนรูปของสัญลักษณ์ทั้งหมดของการรวมรหัสของรหัสที่กำหนด การรวมรหัสอื่นของรหัสเดียวกันจะก่อตัวขึ้น

การรวมรหัสวงจร

การรวมรหัสวงจรด้วย

เมื่อพิจารณารหัสวงจร เลขฐานสองจะแสดงเป็นพหุนาม ซึ่งระดับของ ( พี - 1), พี- ความยาวของชุดรหัส

ตัวอย่างเช่น ชุดค่าผสม 1001111 ( n= 7) จะแสดงด้วยพหุนาม

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

การตรวจจับข้อผิดพลาดโดยใช้รหัสวงกลมทำได้โดยการเลือกชุดค่าผสมที่อนุญาตซึ่งถูกหารโดยไม่เหลือเศษด้วยพหุนามที่เลือกไว้ล่วงหน้า ช(x). หากชุดค่าผสมที่ได้รับมีอักขระที่บิดเบี้ยว ให้หารด้วยพหุนาม ช(x) ดำเนินการกับส่วนที่เหลือ สิ่งนี้สร้างสัญญาณบ่งชี้ข้อผิดพลาด พหุนาม G(x)เรียกว่าสร้าง.

การสร้างชุดค่าผสมของรหัสวงจรทำได้โดยการคูณชุดค่าผสมดั้งเดิม ก(เอ็กซ์) ให้กับพหุนามที่กำลังสร้าง ช(x) ด้วยการลดเงื่อนไขที่คล้ายกัน modulo 2:

• หากกำลังสูงสุดของผลิตภัณฑ์ไม่เกิน ( พี - 1) จากนั้นพหุนามที่ได้จะแสดงถึงการรวมรหัสของรหัสวัฏจักร
• ถ้ากำลังสูงสุดของผลิตภัณฑ์มากกว่าหรือเท่ากับ พีจากนั้นพหุนามผลคูณจะหารด้วยพหุนามดีกรีที่เลือกไว้ล่วงหน้า พีและผลลัพธ์ของการคูณคือส่วนที่เหลือของการหาร

ดังนั้น พหุนามทั้งหมดที่แสดงถึงการผสมรหัสไซคลิกจะมีดีกรีต่ำกว่า พี.

บ่อยครั้งที่เป็นพหุนามที่ใช้การหาร ช(x)= +1 ด้วยการก่อตัวของรหัสผสมเช่นนี้ ตำแหน่งของข้อมูลและสัญลักษณ์ควบคุมไม่สามารถกำหนดล่วงหน้าได้

ข้อได้เปรียบที่สำคัญของรหัสวงจรคือความง่ายในการสร้างตัวเข้ารหัสและตัวถอดรหัส ซึ่งในโครงสร้างของพวกเขาเป็นตัวแทนของ shift registers พร้อมข้อเสนอแนะ

จำนวนบิตของรีจิสเตอร์ถูกเลือกให้เท่ากับระดับของการสร้างพหุนาม

ข้อเสนอแนะดำเนินการจากผลลัพธ์ของการลงทะเบียนไปยังตัวเลขบางหลักผ่าน adders จำนวนที่เลือกโดยสมาชิกที่ไม่ใช่ศูนย์ของการสร้างพหุนาม Adders ถูกติดตั้งที่อินพุตของบิตเหล่านั้นของ register ซึ่งสอดคล้องกับสมาชิกที่ไม่ใช่ศูนย์ของการสร้างพหุนาม

รูปที่ 17 แสดงรูปแบบการลงทะเบียนการเข้ารหัสสำหรับการแปลงชุดค่าผสมสี่บิตเป็นชุดค่าผสมเจ็ดบิต

รูปที่ 17 - แผนผังของการลงทะเบียนการเข้ารหัส

ในตาราง 4 แสดงให้เห็นว่าการเปลี่ยนชุดค่าผสมเดิม 0101 จะได้รับชุดรหัสวงจร 1010011 ได้อย่างไร n= 7, เค=4. ชุดค่าผสม 0101 ป้อนตำแหน่ง 1 ในช่วงสี่รอบแรก รีจิสเตอร์จะถูกกรอก จากนั้นคีย์จะถูกย้ายไปยังตำแหน่ง 2 ข้อเสนอแนะถูกปิด ภายใต้การทำงานของกะเจ็ดรอบ การก่อตัวของรหัสวงจรเจ็ดบิตจะเกิดขึ้น

ตารางที่ 4

คุณสมบัติของรหัสวงจร:

1) รหัสวงจรตรวจพบข้อผิดพลาดเดียวทั้งหมดหากพหุนามที่สร้างมีมากกว่าหนึ่งสมาชิก ถ้า ช(x)=x+ 1 จากนั้นรหัสจะตรวจพบข้อผิดพลาดเดียวและข้อผิดพลาดทั้งหมด

2) รหัสวงจรด้วย ช(x)= (x+ 1)ช(x) ตรวจพบข้อผิดพลาดเดี่ยว สองครั้ง และสามครั้งทั้งหมด

3) รหัสวงจรที่มีพหุนามสร้าง ช(x) องศา r = n - kตรวจจับข้อผิดพลาดของกลุ่มทั้งหมดด้วยระยะเวลา รตัวละคร

ควบคุมคำถาม

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

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

พหุนามลดค่าไม่ได้ในทฤษฎีรหัสวัฏจักรมีบทบาทในการสร้างพหุนาม หากการรวมรหัสที่กำหนดคูณด้วยพหุนามลดค่าไม่ได้ที่เลือก เราจะได้รหัสวงจร ซึ่งความสามารถในการแก้ไขจะถูกกำหนดโดยพหุนามลดค่าไม่ได้

สมมติว่าคุณต้องการเข้ารหัสรหัสไบนารีสี่หลักชุดใดชุดหนึ่ง ให้เราสมมติว่าชุดค่าผสมนี้ G(x) = x 3 + x 2 + 1 ® 1011 โดยไม่พิจารณาถึงการเลือกของเรา เรานำจากตารางของพหุนามที่ลดค่าไม่ได้มาเป็นพหุนามสร้าง P(x) = x 3 + x + 1 ® 1,011 จากนั้นคูณ G(x)เป็นโมโนเมียลระดับเดียวกับพหุนามที่สร้าง จากการคูณพหุนามด้วยเอกนามดีกรี นดีกรีของแต่ละพจน์ของพหุนามจะเพิ่มขึ้น นซึ่งเทียบเท่ากับการกำหนด นศูนย์จากเลขลำดับต่ำของพหุนาม เนื่องจากระดับของพหุนามลดค่าไม่ได้ที่เลือกมีค่าเท่ากับสาม การรวมข้อมูลดั้งเดิมจึงคูณด้วยระดับโมโนเมียลสามระดับ

ก(x) x n =(x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3 = 1101000.

สิ่งนี้ทำเพื่อให้ในภายหลังแทนที่ศูนย์เหล่านี้จะสามารถเขียนบิตแก้ไขได้

ค่าของตัวเลขที่ถูกต้องพบได้จากผลลัพธ์ของการหาร G(x) x nบน พี(x):

x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1

x6 +0+x4 +x3

x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2

x4 + x3 +x2 +0

x 4 + 0 + x 2 + x

x 3 +0+x+0

x 3 +0+x+1

ดังนั้น,

หรือใน ปริทัศน์

ที่ไหน คิว(x)¾เชาวน์ปัญญาและ อาร์(x)¾ส่วนที่เหลือของการหาร ก(x)×xnบน พี(x).

ตั้งแต่ใน เลขคณิตไบนารี 1 Å 1 \u003d 0 ซึ่งหมายถึง -1 \u003d 1 จากนั้นเมื่อเพิ่มเลขฐานสอง คุณสามารถถ่ายโอนเงื่อนไขจากส่วนหนึ่งไปยังอีกส่วนหนึ่งโดยไม่ต้องเปลี่ยนเครื่องหมาย (ถ้าสะดวก) ดังนั้น ความเท่าเทียมกันของแบบฟอร์ม ก อั ข = 0 สามารถเขียนเป็น เอ = บี, แล้วยังไง ก - ข = 0. ความเท่าเทียมกันทั้งสามในกรณีนี้หมายความว่าอย่างใดอย่างหนึ่ง กและ ขเป็น 0 หรือ กและ ขมีค่าเท่ากับ 1 เช่น มีความเท่าเทียมกัน

ดังนั้นนิพจน์ (5.1) สามารถเขียนเป็น

F(x)=Q(x) P(x)= G(x) x n +R(x),

ซึ่งในกรณีตัวอย่างของเราจะให้

ฉ(x)=(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,

ฉ(x)= 1111 1011 = 1101000 + 001 = 1101001.

พหุนาม 1101001 คือชุดค่าผสมที่ต้องการ โดยที่ 1101 คือส่วนข้อมูล และ 001 คืออักขระควบคุม โปรดทราบว่าเราจะได้ชุดค่าผสมที่ต้องการทั้งจากการคูณชุดค่าผสมใดชุดหนึ่งของรหัสไบนารีสี่หลักเต็ม (ในกรณีนี้คือ 1111) ด้วยการสร้างพหุนาม และโดยการคูณชุดค่าผสมที่กำหนดด้วยโมโนเมียลที่มีเหมือนกัน ระดับเป็นพหุนามสร้างที่เลือก (ในกรณีของเรา ชุดค่าผสม 1101000) ได้ด้วยวิธีนี้ ตามด้วยการเพิ่มผลคูณของผลคูณของการแบ่งผลคูณนี้ด้วยผลคูณพหุนาม (ในตัวอย่างของเรา ส่วนที่เหลือมี แบบฟอร์ม 001)

และที่นี่คุณสมบัติของการสร้างพหุนามมีบทบาทชี้ขาด พี(x). วิธีการสร้างรหัสวัฏจักรคือให้พหุนามกำเนิดมีส่วนร่วมในการก่อตัวของการรวมรหัสแต่ละรหัส ดังนั้นพหุนามใด ๆ ของรหัสวัฏจักรจะถูกหารโดยตัวกำเนิดโดยไม่มีเศษเหลือ แต่เฉพาะพหุนามที่เป็นของรหัสที่กำหนดเท่านั้นที่จะถูกหารโดยไม่มีเศษเหลือ นั่นคือ พหุนามที่สร้างให้คุณเลือกชุดค่าผสมที่อนุญาตจากชุดค่าผสมที่เป็นไปได้ทั้งหมด หากเมื่อนำรหัสวงกลมมาหารด้วยการสร้างพหุนาม จะได้เศษที่เหลือ ดังนั้นอาจเกิดข้อผิดพลาดในรหัส หรือนี่คือการรวมกันของรหัสอื่น (การรวมกันที่ผิดกฎหมาย) ตรวจพบส่วนที่เหลือและการมีอยู่ของชุดค่าผสมที่ต้องห้าม เช่น ตรวจพบข้อผิดพลาด เศษที่เหลือจากการแบ่งพหุนามเป็นตัวระบุข้อผิดพลาดในรหัสวงจร

ในทางกลับกัน เศษที่เหลือจากการหารหนึ่งด้วยศูนย์ด้วยการสร้างพหุนามจะใช้ในการสร้างรหัสวงจร

เมื่อหารหน่วยด้วยศูนย์ด้วยการสร้างพหุนาม ควรจำไว้ว่าความยาวของส่วนที่เหลือจะต้องไม่น้อยกว่าจำนวนของบิตควบคุม ดังนั้นในกรณีที่บิตในส่วนที่เหลือไม่เพียงพอ จำนวนที่ต้องการของ ศูนย์มาจากส่วนที่เหลือทางด้านขวา

01100 11111+

เริ่มจากวันที่แปด ส่วนที่เหลือจะถูกทำซ้ำ

ส่วนที่เหลือจากการหารจะใช้ในการสร้างเมทริกซ์การสร้าง ซึ่งเนื่องจากการมองเห็นและความสะดวกในการรับชุดค่าผสมอนุพันธ์จึงถูกใช้อย่างกว้างขวางสำหรับการสร้างรหัสวงจร การสร้างเมทริกซ์การสร้างจะลดลงเป็นการรวบรวมเมทริกซ์เดี่ยวและเมทริกซ์เพิ่มเติมซึ่งเป็นองค์ประกอบที่เหลือของการหารหน่วยด้วยศูนย์ด้วยการสร้างพหุนาม พี(x). จำได้ว่าเมทริกซ์ทรานสโพสประจำตัวคือ เมทริกซ์สี่เหลี่ยม, องค์ประกอบทั้งหมดเป็นศูนย์ ยกเว้นองค์ประกอบที่อยู่ในแนวทแยงมุมจากขวาไปซ้ายจากบนลงล่าง (ในเมทริกซ์ที่ไม่ได้ย้ายตำแหน่ง เส้นทแยงมุมที่มีองค์ประกอบหน่วยจะเรียงจากซ้ายไปขวาจากบนลงล่าง) องค์ประกอบของเมทริกซ์เพิ่มเติมถูกกำหนดให้อยู่ทางขวาของเมทริกซ์การย้ายข้อมูลประจำตัว เฉพาะสิ่งตกค้างน้ำหนักที่ W³d0- 1 ที่ d0- ระยะทางรหัสขั้นต่ำ ความยาวของเรซิดิวต้องเท่ากับจำนวนบิตควบคุมเป็นอย่างน้อย และจำนวนเรซิดิวต้องเท่ากับจำนวนบิตข้อมูล

แถวของเมทริกซ์การสร้างคือชุดค่าผสมแรก รหัสแหล่งที่มา. การรวมรหัสที่เหลือได้มาจากการรวมโมดูโล 2 ของชุดค่าผสมที่เป็นไปได้ทั้งหมดของแถวของเมทริกซ์การสร้าง

ตัวอย่าง.

สร้างเมทริกซ์การสร้างที่สมบูรณ์ของรหัสวงจรที่ตรวจจับข้อผิดพลาดเดี่ยวและคู่ทั้งหมดเมื่อส่งชุดค่าผสมไบนารี 10 บิต

สารละลาย.

ตามตาราง 5.12 เลือกค่าที่ใกล้ที่สุด k ³ 10.

ตาราง 5.12 - ความสัมพันธ์ระหว่างข้อมูลและสัญลักษณ์ตรวจสอบรหัสที่มีความยาวไม่เกิน 16 บิต

น	เค	ρ	น	เค	ρ

ตามตารางจะเป็นค่านี้ k = 11 ในขณะที่ r= 4, ก

n= 15. นอกจากนี้เรายังเลือกการสร้างพหุนาม x 4 + x 3 +1

เราสร้างเมทริกซ์ตัวสร้างที่สมบูรณ์จากเมทริกซ์การย้ายหน่วยในรูปแบบบัญญัติและเมทริกซ์เพิ่มเติมที่สอดคล้องกับหลักตรวจสอบ

เมทริกซ์ทรานสโพสสำหรับ k = 11 ดูเหมือนว่า:

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

เมทริกซ์การสร้างแบบเต็มจะมีลักษณะดังนี้:

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

นอกจากนี้ยังสามารถสร้างเมทริกซ์การสร้างได้โดยการเลื่อนชุดค่าผสมที่ได้จากการคูณแถวของเมทริกซ์เอกลักษณ์ของอันดับ เคเพื่อสร้างพหุนาม

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

แนวคิดของการแก้ไขข้อผิดพลาดนั้นขึ้นอยู่กับข้อเท็จจริงที่ว่าชุดค่าผสมที่ผิดพลาดหลังจากจำนวนรอบของการเปลี่ยนแปลงตามจำนวนที่กำหนดจะถูก "ปรับ" ให้เข้ากับส่วนที่เหลือในลักษณะที่เมื่อรวมกับส่วนที่เหลือจะให้ชุดรหัสที่แก้ไขแล้ว ส่วนที่เหลือในกรณีนี้ไม่มีอะไรนอกจากความแตกต่างระหว่างการบิดเบี้ยวและ สัญลักษณ์ที่ถูกต้องหน่วยในส่วนที่เหลืออยู่ในตำแหน่งของบิตที่บิดเบี้ยวในชุดค่าผสมที่ปรับโดยการเลื่อนแบบวนรอบ ชุดค่าผสมที่บิดเบี้ยวจะถูกปรับจนกว่าจำนวนหน่วยที่เหลือจะเท่ากับจำนวนข้อผิดพลาดในรหัส ในกรณีนี้ จำนวนหน่วยสามารถเท่ากับจำนวนข้อผิดพลาด เอสแก้ไขโดยรหัสนี้ (รหัสแก้ไข 3 ข้อผิดพลาดและ 3 ข้อผิดพลาดในชุดค่าผสมที่ผิดเพี้ยน) หรือน้อยกว่า ส(รหัสแก้ไข 3 ข้อผิดพลาดและในชุดค่าผสมที่ได้รับ 1 ข้อผิดพลาด)

ตำแหน่งของข้อผิดพลาดในการรวมรหัสไม่สำคัญ ถ้า k³(n/2)หลังจากกะจำนวนหนึ่ง ข้อผิดพลาดทั้งหมดจะอยู่ในโซนของการกระทำ "เดี่ยว" ของพหุนามที่สร้าง นั่นคือ ก็เพียงพอแล้วที่จะได้เศษหนึ่งส่วนเหลือ ซึ่งน้ำหนักของ W£และนี่ก็เพียงพอที่จะแก้ไขชุดค่าผสมที่บิดเบี้ยวแล้ว

กระบวนการแก้ไขข้อผิดพลาดมีรายละเอียดด้านล่างโดยใช้ตัวอย่างการสร้างรหัสเฉพาะ

รหัสวงจร

รหัสวงจรเป็นหนึ่งในรหัสระบบบล็อกซึ่งชุดค่าผสมแต่ละชุดจะถูกเข้ารหัสอย่างอิสระ (ในรูปของบล็อก) ในลักษณะที่ข้อมูล k และอักขระควบคุม t จะพบได้เสมอ

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

รหัสวงจรเป็นรหัสที่ลำดับของการกระจายชุดรหัสดำเนินการในลักษณะที่เมื่อส่งผ่านจากชุดค่าผสมใด ๆ ไปยังชุดค่าผสมที่อยู่ใกล้เคียง ระยะห่างของรหัสแฮมมิงจะคงที่ทุกครั้ง

Cyclic codes เป็นตระกูลของรหัสแก้ไขข้อผิดพลาดทั้งหมด ซึ่งรวมถึง Hamming codes ซึ่งเป็นหนึ่งในความหลากหลาย แต่โดยทั่วไปแล้วจะให้ความยืดหยุ่นที่มากกว่าในแง่ของความเป็นไปได้ของการนำรหัสไปใช้ด้วยความสามารถที่จำเป็นในการตรวจจับและแก้ไขข้อผิดพลาดที่เกิดขึ้นเมื่อส่งชุดค่าผสมของรหัส ผ่านช่องทางการติดต่อสื่อสาร รหัสวงจรหมายถึงรหัสบล็อก (n, k) ที่เป็นระบบ โดยที่ k บิตแรกเป็นการผสมกันของรหัสหลัก และบิตต่อมา (n × k) เป็นบิตตรวจสอบ

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

พหุนาม (พหุนาม) ซึ่งสามารถแสดงเป็นผลคูณของพหุนามที่มีดีกรีต่ำกว่า เรียกว่ารีดิวซ์ (ในฟิลด์ที่กำหนด) มิฉะนั้นจะลดทอนไม่ได้ พหุนามลดจำนวนไม่ได้มีบทบาทคล้ายกับจำนวนเฉพาะในทฤษฎีจำนวน พหุนามที่ลดค่าไม่ได้ P(X) สามารถเขียนเป็นเลขฐานสิบหรือเลขฐานสอง หรือเป็นพหุนามเชิงพีชคณิต

กระบวนการเข้ารหัสแบบวนรอบ

การเข้ารหัสแบบวนขึ้นอยู่กับการใช้พหุนามแบบลดค่าไม่ได้ P(X) ซึ่งสัมพันธ์กับรหัสแบบวน เรียกว่าการกำเนิด การกำเนิด หรือการสร้างพหุนาม (โพลิโนเมียล)

ในฐานะที่เป็นสัญลักษณ์ข้อมูล k สำหรับการสร้างรหัสวงจร การรวมรหัสไบนารีสำหรับชุดค่าผสมทั้งหมดจะถูกนำมาใช้ ในกรณีทั่วไป หากนำรหัส Q(x) มาคูณด้วยการสร้างพหุนาม P(x) เราจะได้รหัสวงจรที่มีคุณสมบัติการแก้ไขบางอย่างขึ้นอยู่กับตัวเลือกของ P(x) อย่างไรก็ตาม ในโค้ดนี้ สัญลักษณ์ควบคุม m จะอยู่ในตำแหน่งต่างๆ มากมายในโค้ดเวิร์ด รหัสดังกล่าวไม่เป็นระบบซึ่งทำให้ยากต่อการนำไปใช้ในวงจร สถานการณ์จะง่ายขึ้นอย่างมากหากกำหนดอักขระควบคุมที่ส่วนท้าย ซึ่งก็คือหลังอักขระข้อมูล เพื่อจุดประสงค์นี้ ขอแนะนำให้ใช้วิธีการต่อไปนี้:

คูณโค้ดเวิร์ด G(x) ที่จะเข้ารหัสโดยโมโนเมียล X m ที่มีดีกรีเท่ากันกับโพลิโนเมียล P(x)

เราแบ่งผลิตภัณฑ์ G(x)X m ด้วยการสร้างพหุนาม P(x m):

โดยที่ Q(x) คือผลหารของการหาร R(x) - ส่วนที่เหลือ

การคูณนิพจน์ (2.1) ด้วย Р(x) และโอน R(x) ไปยังส่วนอื่นของความเท่าเทียมกันโดยไม่มีเครื่องหมายย้อนกลับ เราได้รับ:

ดังนั้นตามความเท่าเทียมกัน (2.2) รหัสวงจรนั่นคือข้อความที่เข้ารหัส F(x) สามารถเกิดขึ้นได้สองวิธี:

การคูณหนึ่งรหัสของรหัสไบนารีสำหรับการรวมทั้งหมดโดยการสร้างพหุนาม P(x)

โดยการคูณโค้ดเวิร์ดที่กำหนด G(x) ด้วยพหุนามเดียว X m ที่มีดีกรีเท่ากันกับการสร้างพหุนาม P(x) ด้วยการบวกเศษ R(x) ที่ได้จากการหารผลคูณ G(x)X m ด้วย การสร้างพหุนาม P( X)

การเข้ารหัสข้อความ

จำเป็นต้องเข้ารหัสโค้ดเวิร์ด 1100 ซึ่งสอดคล้องกับ G(x)=x 3 +x 2 กับ P(x)=x 3 +x+1

เราคูณ G (x) ด้วย X m ซึ่งมีดีกรีเป็นที่สาม เราจะได้:

หารผลิตภัณฑ์ G(x)X m ด้วยการสร้างพหุนาม P(x m) ตาม (2.1) เราได้รับ:

หรือเทียบเท่าไบนารี:

ด้วยเหตุนี้ เราจึงได้ผลหาร Q(x) ในระดับเดียวกับ G(x):

Q(x)=x 3 +x 2 +x>1110

และที่เหลือ:

เป็นผลให้การรวมรหัสไบนารีที่เข้ารหัสโดยรหัสวงจรตาม (2.2) จะอยู่ในรูปแบบ:

F(x)=1110 1011=1100010

เนื่องจากการรวมรหัสที่อนุญาตแต่ละรหัสของรหัสวงกลมแสดงถึงผลรวมที่เป็นไปได้ทั้งหมดของการสร้างพหุนาม G(x) จึงต้องหารด้วย P(x) โดยไม่เหลือเศษ ดังนั้น การตรวจสอบความถูกต้องของการรวมโค้ดที่ได้รับจึงลดลงเหลือเพียงการระบุส่วนที่เหลือเมื่อหารด้วยการสร้างพหุนาม

การรับส่วนที่เหลือแสดงว่ามีข้อผิดพลาด ส่วนที่เหลือของรหัสวัฏจักรเล่นบทบาทของซินโดรม

ตัวอย่างเช่น การรวมโค้ดที่ส่ง F(x)=1100010 สร้างขึ้นโดยใช้การสร้างพหุนาม P(x)=1011 ภายใต้อิทธิพลของการรบกวน การรวมรหัสถูกเปลี่ยนเป็นชุดค่าผสม F "(x) = 1000010

เราแบ่งชุดค่าผสมที่ได้รับด้วยการสร้างพหุนาม

การมีอยู่ของส่วนที่เหลือ R(x)=001 แสดงว่ามีข้อผิดพลาด อย่างไรก็ตาม ไม่ได้ระบุตำแหน่งของข้อผิดพลาดในชุดค่าผสมโดยตรง เพื่อระบุข้อผิดพลาดมีหลายวิธีตามการวิเคราะห์กลุ่มอาการ

มากำหนดตำแหน่งของข้อผิดพลาดกัน สำหรับสิ่งนี้ เราจะแบ่งหน่วยด้วยจำนวนศูนย์โดยพลการโดย P(x)=1011

เกิดข้อผิดพลาดในหมายเลของค์ประกอบ:

จำนวนของสารตกค้าง -2>4-2=2

นั่นคือข้อผิดพลาดอยู่ในองค์ประกอบที่สอง

มหาวิทยาลัยแห่งรัฐเบลารุสของวิทยาศาสตร์ข้อมูลและวิทยุอิเล็กทรอนิกส์

กรมสรรพากร

บทคัดย่อในหัวข้อ:

รหัสวงจร รหัส BCH"

มินสค์, 2552

รหัสวงจร

รหัสวงจรเป็นบล็อกเชิงเส้น (n,k) -รหัสซึ่งมีลักษณะเฉพาะโดยคุณสมบัติของวงจรเช่น การเลื่อนไปทางซ้ายทีละขั้นตอนของโค้ดเวิร์ดที่อนุญาตยังให้โค้ดเวิร์ดที่อนุญาตที่เป็นของโค้ดเดียวกันและชุดของโค้ดเวิร์ดนั้นแทนด้วยชุดของพหุนามระดับ (n-1) หรือน้อยกว่า หารด้วยพหุนาม g(x) ของดีกรี r = n-k ซึ่งเป็นตัวประกอบของทวินาม x n +1

พหุนาม g(x) เรียกว่าการกำเนิด

จากคำจำกัดความ โค้ดเวิร์ดในโค้ดวงกลมจะแสดงเป็นพหุนาม

โดยที่ n คือความยาวของรหัส - ค่าสัมประสิทธิ์จากสนาม GF(q)

หากรหัสถูกสร้างขึ้นบนฟิลด์ GF(2) ดังนั้นค่าสัมประสิทธิ์จะใช้ค่า 0 หรือ 1 และรหัสนั้นเรียกว่าไบนารี
ตัวอย่าง.ถ้ารหัสของรหัสวงจร

จากนั้นพหุนามที่สอดคล้องกัน

ตัวอย่างเช่น หากรหัสถูกสร้างขึ้นบนฟิลด์ GF(q)=GF(2 3) ซึ่งเป็นส่วนขยายของโมดูโล GF(2) และพหุนามที่ลดค่าไม่ได้ f(z)=z 3 +z+1 และองค์ประกอบต่างๆ ของช่องนี้มีแบบแสดงไว้ในตารางที่ 1

แล้วค่าสัมประสิทธิ์

ใช้ค่าขององค์ประกอบของฟิลด์นี้และดังนั้นจึงแสดงเป็นพหุนามของแบบฟอร์มต่อไปนี้
โดยที่ m คือดีกรีของพหุนามที่ขยายเขตข้อมูล GF(2) ผม - ค่าสัมประสิทธิ์ที่ใช้ค่าขององค์ประกอบของ GF(2), เช่น 0 และ 1 รหัสดังกล่าวเรียกว่า q-th

ความยาวของรหัสวงจรเรียกว่า ดั้งเดิม และรหัสนั้นเรียกว่า ดั้งเดิม ถ้าความยาวของมันคือ n=q m -1 บน GF(q)

หากความยาวของรหัสน้อยกว่าความยาวของรหัสดั้งเดิม รหัสนั้นจะถูกเรียกว่า shortened หรือ non-primitive

จากคำจำกัดความ คุณสมบัติทั่วไปของคำรหัสของรหัสวัฏจักรคือการหารโดยไม่เหลือเศษด้วยพหุนาม g(x) เรียกว่าตัวสร้าง

ผลลัพธ์ของการหารทวินาม x n +1 ด้วยพหุนาม g(x) คือพหุนามทดสอบ h(x)

เมื่อถอดรหัสรหัสวงจร จะใช้ข้อผิดพลาดพหุนาม e(x) และพหุนามซินโดรมิก S(x)

พหุนามข้อผิดพลาดของระดับไม่เกิน (n-1) ถูกกำหนดจากนิพจน์

โดยที่พหุนามเป็นตัวแทนของคำรหัสที่ได้รับ (ผิดพลาด) และรหัสที่ส่งตามลำดับ

ค่าสัมประสิทธิ์ที่ไม่เป็นศูนย์ใน e(x) อยู่ในตำแหน่งที่สอดคล้องกับข้อผิดพลาด

ตัวอย่าง.

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

หรือ

ดังนั้น พหุนามกลุ่มอาการขึ้นอยู่กับข้อผิดพลาดพหุนาม e(x) โดยตรง บทบัญญัตินี้ใช้ในการสร้างตารางกลุ่มอาการที่ใช้ในกระบวนการถอดรหัส ตารางนี้ประกอบด้วยรายการพหุนามผิดพลาดและรายการกลุ่มอาการที่เกี่ยวข้องซึ่งพิจารณาจากนิพจน์

(ดูตารางที่ 2)

ในกระบวนการถอดรหัสซินโดรมจะคำนวณจากคำรหัสที่ได้รับจากนั้นพบพหุนาม e(x) ที่สอดคล้องกันในตารางซึ่งผลรวมของคำรหัสที่ได้รับจะให้คำรหัสที่ถูกต้องเช่น

พหุนามที่แสดงรายการสามารถเพิ่ม คูณ และหารโดยใช้กฎที่ทราบของพีชคณิต แต่ด้วยผลลัพธ์ที่ลดลง mod 2 แล้วจึง mod x n +1 หากระดับของผลลัพธ์เกินระดับ (n-1)

สมมติว่าความยาวของโค้ดคือ n=7 จากนั้นเราจะให้ผลลัพธ์ของ mod x 7 +1

เมื่อสร้างและถอดรหัสรหัสวัฏจักร อันเป็นผลจากการแบ่งพหุนาม โดยปกติแล้วไม่จำเป็นต้องมีผลหาร แต่เป็นเศษเหลือจากการหาร
ดังนั้น ขอแนะนำให้ใช้วิธีการหารที่ง่ายกว่า โดยไม่ใช้พหุนาม แต่ใช้เฉพาะค่าสัมประสิทธิ์เท่านั้น (ตัวเลือกที่ 2 ในตัวอย่าง)

ตัวอย่าง.

การกำหนดเมทริกซ์ของรหัส

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

และ

เมื่อสร้างเมทริกซ์ H (n,k) ค่าสัมประสิทธิ์นำหน้าของพหุนาม h(x) จะอยู่ทางด้านขวา

ตัวอย่าง.สำหรับรหัสวงจร (7,4) ที่มีการสร้างพหุนาม g(x)=x 3 +x+1 เมทริกซ์ G (n,k) และ H (n,k) มีรูปแบบ:

ที่ไหน

สำหรับรหัสวงจรอย่างเป็นระบบ เมทริกซ์ G (n,k) ถูกกำหนดจากนิพจน์

โดยที่ k คือเมทริกซ์เอกลักษณ์ R k,r - เมทริกซ์สี่เหลี่ยม แถวของเมทริกซ์ R k,r ถูกกำหนดจากนิพจน์หรือโดยที่ a (x) คือค่าของแถวที่ i ของเมทริกซ์ I k ; ผม - หมายเลขแถวของเมทริกซ์ R k,r .

ตัวอย่าง.เมทริกซ์ G (n,k) สำหรับ (7,4)-รหัสตามการสร้างพหุนาม g(x)=x 3 +x+1 ถูกสร้างขึ้นในลำดับต่อไปนี้

หรือ

R 4.3 ถูกกำหนดโดยใช้

เพราะ

ในทำนองเดียวกันจะถูกกำหนด