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

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

พหุนามที่สร้างเป็นการแทนค่าไบนารีของหนึ่งในปัจจัยง่าย ๆ ที่ทำให้ตัวเลข X n -1 ถูกทำลาย โดยที่ X n หมายถึงหนึ่งในหลักที่ n, n เท่ากับจำนวนหลักของกลุ่มรหัส ดังนั้น ถ้า n = 10 และ X = 2 ดังนั้น X n -1 = 1,023 = 11*93 และถ้า g(X) = 11 หรือในรหัสไบนารี่ 1011 แล้วตัวอย่างของรหัสวงจร A i *g(X) ตัวเลข A i ในกลุ่มโค้ดที่มีพหุนามที่สร้างนี้สามารถดูได้ในตารางต่อไปนี้ 3.1.

ตัวเลือกพื้นฐานรหัสวงจรซึ่งใช้กันอย่างแพร่หลายในทางปฏิบัติ แตกต่างจากรหัสก่อนหน้านี้ตรงที่การดำเนินการของการหารด้วยพหุนามที่สร้างถูกแทนที่ด้วยอัลกอริทึมต่อไปนี้: 1) ค่าศูนย์ K ถูกกำหนดให้กับรหัสเดิมหมายเลข A ทางด้านขวา โดยที่ K คือ จำนวนบิตในพหุนามที่สร้าง ลดลงหนึ่ง 2) การดำเนินการ O จะดำเนินการกับผลลัพธ์จำนวน A*(2 K) ซึ่งแตกต่างจากการหารตรงที่ในแต่ละขั้นตอนของการดำเนินการ แทนที่จะลบ จะดำเนินการแบบ "เฉพาะ OR" ระดับบิต: 3) ผลลัพธ์ส่วนที่เหลือ B คือ CRC - รหัส K-bit ซ้ำซ้อนซึ่งแทนที่ในหมายเลขที่เข้ารหัส C เลขศูนย์ที่กำหนดทางด้านขวาให้กับ K เช่น

C= ก*(2 K)+B

ที่ฝั่งรับ การดำเนินการ O จะดำเนินการกับโค้ด C หากส่วนที่เหลือไม่เป็นศูนย์ แสดงว่าเกิดข้อผิดพลาดระหว่างการส่ง และโค้ด A จะต้องถูกส่งอีกครั้ง

ตัวอย่าง ให้ A = 1001 1101 สร้างพหุนาม 11001

เนื่องจาก K = 4 ดังนั้น A*(2 K)=100111010000 การดำเนินการของการดำเนินการ O สำหรับการคำนวณรหัสวงจรจะแสดงในรูปที่ 1 3.2.

ตารางที่ 3.1

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

ข้าว. 3.2. ตัวอย่างการรับรหัสไซเคิล

โค้ดแบบวนเป็นโค้ดเชิงเส้น ซึ่งเป็นเซตจำกัดที่ถูกปิดภายใต้การดำเนินการของการเปลี่ยนแปลงแบบวนของเวกเตอร์โค้ดที่ก่อตัวเป็นโค้ดนั้น ให้มันได้รับ n-มิติเวกเตอร์ โวลต์ = ก 0 ก 1 …หนึ่ง-1 พร้อมพิกัดจากสนามสุดท้าย เอฟ- การเปลี่ยนแปลงแบบวนเรียกว่าเวกเตอร์ วี"= ก n-1 ก 0 ก 1 … หนึ่ง -2 .

ลองพิจารณาดู n-ปริภูมิเลขคณิตมิติเหนือสนามกาลัวส์ กฟ(2). เวกเตอร์แต่ละตัว ก 0 ก 1 …หนึ่ง-1 จาก กฟ(2) เราสามารถเปรียบเทียบพหุนามแบบหนึ่งต่อหนึ่งได้ ก 0 +ก 1 x+…+หนึ่ง -1 เอ็กซ์เอ็น-1 โดยมีอัตราต่อรองจาก กฟ(2). ผลรวมของเวกเตอร์สองตัว ก 0 ก 1 …หนึ่ง-1 และ ข 0 ข 1 …บีเอ็น-1 ถูกจัดเรียงโดยสอดคล้องกับผลรวมของพหุนามที่สอดคล้องกับพวกมัน ผลคูณขององค์ประกอบสนามด้วยเวกเตอร์ - ผลคูณของพหุนามที่สอดคล้องกับเวกเตอร์นี้ด้วยองค์ประกอบ

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

รหัสเชิงเส้นที่เกิดจากคลาสของพหุนาม ค(ก(x)) ผลคูณของพหุนามบางตัว ก(x) เรียกว่าพหุนามกำเนิด เรียกว่าพหุนาม

เรามาแสดงให้เห็นว่ารหัสพหุนามเกี่ยวข้องกันอย่างไร ค(ก(x)) และรหัสวงจร อนุญาต ก = ก 0 …หนึ่ง-1 คือคำรหัสบางส่วนและพหุนามรหัสที่สอดคล้องกัน ก(x) = ก 0 +...+หนึ่ง -1 เอ็กซ์เอ็น-1. วงจรการเปลี่ยนแปลง ก" สอดคล้องกับรหัสพหุนาม ก"(x) = หนึ่ง -1 +ก 0 x+…+หนึ่ง -2 x n -1 ซึ่งสามารถแสดงในรูปของต้นฉบับ:

เนื่องจากรหัสพหุนามจะต้องหารด้วย ก(x) จากนั้นเพื่อให้มันเป็นวงจร นั่นคือพหุนาม ก"(x) ต้องหารด้วย ก(x- จากการพิจารณานี้ เราสามารถกำหนดทฤษฎีบทต่อไปนี้ได้ รหัสพหุนามจะเป็นแบบวนก็ต่อเมื่อเป็นพหุนามเท่านั้น ก(x) เป็นตัวหารของพหุนาม เอ็กซ์เอ็น–1. ในกรณีนี้คือพหุนาม ก(x) เรียกว่าพหุนามการสร้างของรหัสไซคลิก

ในทฤษฎีการเข้ารหัส ทฤษฎีบทต่อไปนี้ได้รับการพิสูจน์แล้ว: ถ้าเป็นพหุนาม ก(x) มีวุฒิการศึกษา n–เคและเป็นตัวหาร เอ็กซ์เอ็น–1 จากนั้น ค(ก(x)) เป็นวงจรเชิงเส้น ( n, เค)-รหัส.

พหุนาม เอ็กซ์เอ็น–1 แยกตัวประกอบ เอ็กซ์เอ็น–1 = (x–1)(เอ็กซ์เอ็น -1 +เอ็กซ์เอ็น-1 +…+1) ดังนั้นจึงมีรหัสวงจรสำหรับรายการใดๆ n- จำนวนไซคลิก nรหัสบิตเท่ากับจำนวนตัวหารของพหุนาม เอ็กซ์เอ็น–1. ตารางส่วนขยายพหุนามได้รับการพัฒนาเพื่อสร้างรหัสวงจร เอ็กซ์เอ็น–1 เป็นพหุนามที่ลดทอนไม่ได้ กล่าวคือ เป็นพหุนามที่หารด้วยเอกภาพเท่านั้นและด้วยตัวมันเองเท่านั้น

ลองพิจารณาดูว่าโค้ดใดที่สามารถสร้างได้จากพหุนาม x 7-1 เหนือสนาม กฟ(2). การขยายตัวของพหุนามไปสู่ปัจจัยที่ลดไม่ได้นั้นมีรูปแบบ

เนื่องจากเป็นไปได้ที่จะสร้างตัวหารหกตัวของพหุนามได้ x 7–1 เมื่อรวมตัวหารที่ลดไม่ได้แล้ว จะได้รหัสไบนารี่ไซคลิกหกรหัส - n, เค)-code ถูกกำหนดโดยค่าเป็นอันดับแรก nและประการที่สอง ค่า เค = n – ส, ส– ระดับของตัวหารพหุนาม เอ็กซ์เอ็น–1 ซึ่งกำหนดรหัส ด้านล่างนี้คือตัวหารพหุนามและค่าที่เกี่ยวข้อง เค:

x – 1, ส=1, เค=6;

x 3 +x 2 +1, ส=3, เค=4;

x 3 +x+1, ส=3, เค=4;

(x–1)(x 3 +x 2 +1)=x 4 +x 2 +x+1, ส=4, เค=3;

(x–1)(x 3 +x+1)=x 4 +x 3 +x 2 +1, ส=4, เค=3;

(x 3 +x 2 +1)(x 3 +x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, ส=6, เค=1.

รหัส (7, 6) มีสัญลักษณ์ตรวจสอบเพียงอันเดียว และรหัส (7, 1) มีสัญลักษณ์ข้อมูลเพียงอันเดียว ตามลำดับคือรหัสตรวจสอบความเท่าเทียมกันและรหัสการทำซ้ำ

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

ให้เราพิจารณาว่าอย่างไรโดยใช้พหุนามการสร้าง ก(x) = 1+x+xการเข้ารหัส 3 ดำเนินการด้วยรหัส (7, 4) ยกตัวอย่างเช่น คำขนาด 4 บิต (0101) ซึ่งสอดคล้องกับพหุนาม ฉ(x) = x + x 3. การคูณพหุนามสองตัวนี้

รหัสวงจร

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

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

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

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

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

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

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

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

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

เราคูณรหัสรวมกัน G(x) ที่ต้องเข้ารหัสโดย monomial X m ที่มีระดับเดียวกันกับพหุนามที่สร้าง P(x)

เราหารผลคูณ G(x)х m ด้วยพหุนามที่สร้าง Р(х m):

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

เมื่อคูณนิพจน์ (2.1) ด้วย P(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)х m ด้วยพหุนามที่สร้าง Р(х m) ตาม (2.1) ที่เราได้รับ:

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

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

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

และส่วนที่เหลือ:

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

ฉ(x)=1110 1,011=1100010

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

การรับยอดคงเหลือบ่งชี้ว่ามีข้อผิดพลาดเกิดขึ้น ส่วนที่เหลือของการหารในรหัสวงจรมีบทบาทเป็นกลุ่มอาการ

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

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

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

เรามาพิจารณาตำแหน่งของข้อผิดพลาดกัน โดยหารค่าหนึ่งด้วยจำนวนศูนย์ตามใจชอบด้วย P(x) = 1,011

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

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

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

คุณสมบัติหลักและชื่อของรหัสแบบวนนั้นเกี่ยวข้องกับข้อเท็จจริงที่ว่าการผสมสัญลักษณ์ไบนารี่ที่อนุญาตทั้งหมดในข้อความที่ส่งสามารถได้รับโดยการดำเนินการของการเปลี่ยนแปลงแบบวนของคำต้นฉบับบางคำ: โดยทั่วไปแล้ว การผสมรหัสของรหัสแบบวงจรคือ ถือว่าไม่ใช่ลำดับของเลขศูนย์และเลข แต่เป็นพหุนามของบางองศา จำนวนใดๆ ในระบบตัวเลขตำแหน่งใดๆ สามารถแสดงในรูปแบบทั่วไปได้ดังนี้ โดยที่ x เป็นฐานของระบบตัวเลข เอ - ตัวเลขของระบบตัวเลขที่กำหนด p-1, p-2,... - ตัวบ่งชี้กำลังที่ฐานถูกยกขึ้นและในเวลาเดียวกันคือหมายเลขซีเรียลที่ใช้ตัวเลข สำหรับระบบไบนารี่ x = 2 และ a อาจเป็น “O” หรือ “1” ตัวอย่างเช่น ชุดค่าผสมไบนารี 01001 สามารถเขียนเป็นพหุนามของอาร์กิวเมนต์ x ได้: เมื่อเขียนการรวมโค้ดเป็นพหุนาม หน่วยในหลักที่ 1 จะเขียนเป็นคำว่า "x" และศูนย์จะไม่เขียนเลย . การแสดงการรวมรหัสในรูปแบบของพหุนามช่วยให้คุณสร้างการติดต่อแบบหนึ่งต่อหนึ่งระหว่างพวกเขาและลดการดำเนินการในการรวมกันเป็นการกระทำบนพหุนาม ดังนั้นการเติมพหุนามไบนารี่จะลดลงเหลือเพียงการบวกแบบโมดูโล 2 ค่าสัมประสิทธิ์ ยกกำลังของตัวแปร ตัวอย่างเช่น การคูณจะดำเนินการตามกฎปกติสำหรับการคูณฟังก์ชันกำลัง แต่ค่าสัมประสิทธิ์ผลลัพธ์สำหรับระดับที่กำหนดจะถูกเพิ่มแบบโมดูโล 2 ตัวอย่างเช่น การหารก็ดำเนินการเหมือนการหารพหุนามตามปกติ ในกรณีนี้ การดำเนินการลบจะถูกแทนที่ด้วยการดำเนินการแบบโมดูโล 2 เพิ่มเติม: ตามที่ระบุไว้ข้างต้น รหัสนี้เรียกว่าวงจรเนื่องจากวงจรเปลี่ยน a n ^ a l L,..., a 2, a 1, a d1 a n1 ของชุดค่าผสมที่อนุญาต a n (, a n _ 2,..., a 1, และ 0 เป็นการรวมกันที่ได้รับอนุญาต การเรียงสับเปลี่ยนแบบวนดังกล่าวเมื่อใช้การแทนในรูปแบบของพหุนามนั้นเกิดขึ้นจากการคูณพหุนามนี้ด้วย x ถ้า Y(x) = a pL x n1 + a n2 x n " 2 + ... + a ( x + a 0 จากนั้น Y (x) x = a n] x n + a n 2 xn " 1 +... + a x x 2 + a^x เพื่อให้ดีกรีของพหุนามไม่เกิน n-1 คำว่า x" ถูกแทนที่ด้วยหนึ่ง ดังนั้น: ตัวอย่างเช่น เรามีรหัสรวมกัน 1101110->x ใน +x 5 +x 3 +.x g -1-x ลองเลื่อนมันไปหนึ่งหลัก เรา ได้รับ: ซึ่งเหมือนกับการคูณพหุนามดั้งเดิมบน x: ทฤษฎีการสร้างรหัสวงจรขึ้นอยู่กับส่วนของพีชคณิตขั้นสูงที่ศึกษาคุณสมบัติของพหุนามไบนารี บทบาทพิเศษในทฤษฎีนี้เล่นโดยสิ่งที่เรียกว่าพหุนามที่ลดไม่ได้ นั่นคือพหุนามที่ไม่สามารถแสดงเป็นผลคูณของพหุนามที่มีดีกรีต่ำกว่าได้ สมาชิกจะหารด้วยตัวมันเองและหนึ่งลงตัวเท่านั้น จากพีชคณิตชั้นสูงเป็นที่ทราบกันดีว่าทวินาม x"+1 ถูกหารโดยไม่เหลือเศษด้วยพหุนามที่ลดไม่ได้ ในทฤษฎีการเข้ารหัส พหุนามที่ลดไม่ได้ถูกเรียกว่าการสร้างพหุนาม เนื่องจากพวกมัน "สร้าง" อนุญาตให้ใช้รหัสผสมกัน (พหุนามที่ลดไม่ได้จะถูกจัดเป็นตาราง ดูตารางที่ 8.4 ) (9) แนวคิดในการสร้างรหัสแบบวนลงมาคือพหุนามที่เป็นตัวแทนส่วนข้อมูลของการรวมรหัสจะต้องแปลงเป็นพหุนามระดับไม่เกิน n-1 ซึ่งหารลงตัวโดยไม่มี ส่วนที่เหลือจากการสร้างพหุนาม P(x) สิ่งสำคัญคือระดับของค่าหลังจะต้องสอดคล้องกับจำนวนหลัก ตรวจสอบส่วนหนึ่งของการรวมโค้ด การหารลงตัวโดยไม่มีเศษเหลือด้วยการสร้างพหุนาม P(x) การสร้างการรวมรหัสที่อนุญาตจะลดลงดังต่อไปนี้: 1. เราแสดงส่วนข้อมูลของการรวมรหัสที่มีความยาว k ในรูปแบบของพหุนาม O(x) . 3. แบ่งพหุนาม O(x)x" ออกเป็นพหุนามที่สร้าง P(x) ซึ่งมีดีกรีเท่ากับ r จากผลของการคูณ O(x) ด้วย xr จะได้ดีกรีของโมโนเมียลแต่ละตัวที่รวมอยู่ใน O( x) เพิ่มขึ้นด้วย r เมื่อหารผลคูณของ x g O[x) ด้วยพหุนามการสร้างระดับ r จะได้ผลหาร C(x) ในระดับเดียวกับ 0(x) ผลลัพธ์ของการดำเนินการเหล่านี้สามารถแสดงได้ใน รูปร่าง: (8.28) โดยที่ R(x) คือเศษที่เหลือจากการหาร 0(x)x r ด้วย P(x) เนื่องจาก C(x) มีระดับเท่ากับ 0(x) ดังนั้น C(x) จึงเป็นการรวมรหัสของรหัส ¿-บิตเดียวกัน ระดับของส่วนที่เหลือไม่สามารถจะมากกว่าระดับของพหุนามกำเนิดได้ กล่าวคือ ระดับสูงสุดของมันคือเท่ากับ r-1 ดังนั้น จำนวนหลักที่มากที่สุดของเศษที่เหลือจะต้องไม่เกิน r เมื่อคูณทั้งสองข้างของ (8.28) ด้วย P(x) การรวบรวมข้อมูล: (8.29) (เครื่องหมายลบจะถูกแทนที่ด้วยเครื่องหมายบวกแบบโมดูโล 2) แน่นอนว่า F(x) หารด้วย P(x) ลงตัวโดยไม่มีเศษ พหุนาม F(x) แสดงถึงรูปแบบที่อนุญาตของรหัสวงจร จาก (8.29) ตามมาว่าการรวมรหัสที่อนุญาตของรหัสไซคลิกสามารถรับได้สองวิธี: โดยการคูณรหัสรวมกันของรหัสอย่างง่าย C(x) ด้วยการสร้างพหุนาม P(x) หรือการคูณรหัสรวมกัน 0( x) ของโค้ดอย่างง่ายด้วยโมโนเมียล x r โดยการบวกเข้ากับผลคูณของส่วนที่เหลือ P(x) ซึ่งได้จากการหารผลคูณด้วยพหุนามที่สร้าง P(x) ด้วยวิธีการเข้ารหัสวิธีแรก ข้อมูลและบิตการตรวจสอบจะไม่แยกออกจากกัน (รหัสจะแยกกันไม่ออก) ทำให้กระบวนการถอดรหัสยากต่อการปฏิบัติในทางปฏิบัติ ด้วยวิธีที่สอง จะได้รับรหัสที่แยกได้: บิตข้อมูลจะอยู่ในตำแหน่งสูงสุด ส่วนบิต p-c ที่เหลือจะเป็นบิตสำหรับการตรวจสอบ วิธีการเข้ารหัสนี้ใช้กันอย่างแพร่หลายในทางปฏิบัติ ตัวอย่างที่ 3 กำหนดรหัสรวมกัน 0111 มาสร้างรหัสวงจรด้วย d o = 3 กัน วิธีแก้ไข ในระยะแรกตามค่า d o = 3 ที่ต้องการ เราจะกำหนดความยาวของโค้ด l และจำนวนองค์ประกอบตรวจสอบ k ในการดำเนินการนี้ เราใช้ตาราง 8.6.1 สำหรับรหัสสี่หลักที่กำหนด N-16 จากนั้นสำหรับ d = 3 จากความสัมพันธ์ 16 (ตารางที่ 8.3) เราพบ n - 7 ตามลำดับ k = n - m - = 7 - 4 = 3 ดังนั้นจึงจำเป็นต้องมีโค้ด (7.4) เมื่อใช้ตารางการสร้างพหุนาม (ตาราง 8.4) สำหรับ k = 3 เราจะหา P(x) = x 3 + x 2 + 1 ถัดไป: 1) สำหรับข้อความ 0111 เรามี O(x) = x 2 + x + 1 ; 2) คูณ 0(x) ด้วย x 3 (เนื่องจาก r = 3): O(x) x 3 = (x 2 -I- x + 1) x 3 = x 5 + x 4 + x 3; 3) หาร (E(x)x 3 ด้วย P(x): 4) เราได้รับ: ^(x) = O (x) x 3 0 R (x) = x 5 + x 4 + x 3 + 1 พหุนามนี้สอดคล้องกับการรวมรหัส: การดำเนินการข้างต้นทั้งหมดสามารถทำได้กับเลขฐานสอง: ตารางที่ 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001 ให้เราสร้างชุดโค้ดที่อนุญาตด้วยวิธีแรก: F( x)=C( x)พี(x). มาคูณกันโดยแทนพหุนามเป็นเลขฐานสอง: จะเห็นได้ว่าในผลลัพธ์การรวมรหัสนั้น ไม่สามารถแยกแยะข้อมูลและบิตการตรวจสอบได้ การตรวจจับข้อผิดพลาดระหว่างการเข้ารหัสแบบวนนั้นมาจากการแบ่งชุดรหัสที่ได้รับด้วยพหุนามที่สร้างแบบเดียวกับที่ใช้ระหว่างการเข้ารหัส (ต้องทราบประเภทของรหัสที่แผนกต้อนรับ) หากไม่มีข้อผิดพลาดในการรวมรหัสที่ได้รับ (หรือเป็นเช่นนั้นว่าชุดรหัสที่ส่งที่กำหนดถูกแปลงเป็นชุดอื่นที่ได้รับอนุญาต) การหารด้วยพหุนามที่สร้างจะดำเนินการโดยไม่มีเศษเหลือ หากการหารส่งผลให้มีเศษเหลือ แสดงว่ามีข้อผิดพลาดเกิดขึ้น ตัวอย่างที่ 4 เนื่องจากเป็นการรวมรหัสที่อนุญาต เราใช้การรวมรหัสที่ได้รับในตัวอย่างก่อนหน้านี้: P(x) = x 5 + x 4 + x 3 + 1 และ P(x) = x 3 + x 2 +1 หรือในรูปแบบไบนารี่ E(0,1) = 0111001; P(0,1) = 1101 สมมติว่าในส่วนของข้อมูลเกิดข้อผิดพลาดในหลักที่สำคัญที่สุด (ที่ 7) (เรานับหลักจากขวาไปซ้าย) ชุดรหัสที่ยอมรับจะมีลักษณะเป็น 1111001 มาดำเนินการตรวจหาข้อผิดพลาดกันดีกว่า: การมีอยู่ของสารตกค้างที่ 110 บ่งชี้ว่ามีข้อผิดพลาด รหัสแบบวนใช้กันอย่างแพร่หลายในระบบการส่งข้อมูล ตัวอย่างเช่น ในโปรโตคอลโมเด็มที่ใช้กันอย่างแพร่หลาย \7.42 ในการเข้ารหัสกลุ่มโค้ด จะใช้การสร้างพหุนาม d(X) = X 16 + X" -2 + X 5 + 1 ซึ่งเทียบเท่ากับรหัส 1 0001 0000 0010 0001 เช่นเดียวกับลำดับที่สูงกว่าที่สร้างพหุนาม d(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + เอ็กซ์ 2 + 1.8.6.

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

ตัวอย่าง. สร้างรหัสไซคลิกสำหรับ เนื่องจากพหุนามที่สร้างเป็นพหุนามของดีกรีที่ 1 ซึ่งเป็นจำนวนหลักตรวจสอบ ดังนั้น ในการสร้างรหัสไซคลิก เราจึงสร้างเมทริกซ์ที่สร้าง

ในการสร้างเมทริกซ์เพิ่มเติม เราจะค้นหาเศษที่เหลือจากการหารแถวสุดท้ายของเมทริกซ์ที่ย้ายหน่วย ซึ่งมีเลข 0 เสริมด้วยพหุนามที่เลือก:

ดังนั้นเมทริกซ์ C,k เพิ่มเติมจึงมีรูปแบบ

ตอนนี้เราสร้างเมทริกซ์กำเนิด

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

ตารางที่ 39 (ดูการสแกน)

สิ่งที่น่าสนใจที่รู้จักกันดีคือการพิจารณาโค้ดที่ง่ายที่สุดต่อไปนี้ที่สร้างขึ้นโดยใช้พหุนามที่ลดไม่ได้ของดีกรีที่สอง

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

เป็นเรื่องง่ายที่จะตรวจสอบว่าเมื่อหารด้วยพหุนามที่สร้างที่กำหนด โมโนเมียลจะแสดงสตริง

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