รหัสวงจร

รหัสแบบวนเป็นหนึ่งในรหัสระบบของบล็อก ซึ่งแต่ละชุดจะถูกเข้ารหัสอย่างเป็นอิสระ (ในรูปแบบของบล็อก) ในลักษณะที่ข้อมูล 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)=1011

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

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

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

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

กรมวิทย์

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

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

มินสค์, 2009

รหัสวงจร

รหัสไซคลิกคือรหัสบล็อกเชิงเส้น (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

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

หากความยาวของโค้ดน้อยกว่าความยาวของโค้ดดั้งเดิม โค้ดนั้นจะถูกเรียกว่าแบบสั้นหรือไม่ใช่แบบดั้งเดิม

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

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

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

พหุนามความคลาดเคลื่อนของดีกรีไม่เกิน (n-1) ถูกกำหนดจากนิพจน์

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

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

ตัวอย่าง.

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

หรือ

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

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

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

พหุนามที่ระบุไว้สามารถเพิ่ม คูณ และหารได้โดยใช้กฎพีชคณิตที่ทราบ แต่ด้วยผลลัพธ์ที่กำหนด mod 2 จากนั้น mod xn +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) จะถูกกำหนดจากนิพจน์

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

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

หรือ

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

เพราะ

กำหนดในลักษณะเดียวกัน

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

รหัสระบบสื่อสารทนเสียงรบกวนที่สำคัญที่สุดหลายประการ ได้แก่

โดยเฉพาะอย่างยิ่งวงจร บนพื้นฐานของโครงสร้างอันจำกัดทางคณิตศาสตร์

ทุ่งกาลัวส์ สนามคือเซตขององค์ประกอบที่มีสนามจำกัด

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

1 Evariste Galois (1811 - 1832) - นักคณิตศาสตร์ชาวฝรั่งเศส ผู้วางรากฐานของพีชคณิตสมัยใหม่

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

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

สำหรับการดำเนินการบวกและการคูณ ให้ปฏิบัติตามกฎทางคณิตศาสตร์ตามปกติของการเชื่อมโยงกัน - ก + (ข + ค) = (ก + ข)+ c การสับเปลี่ยน - ก + ข = ข + กและ ก ข = ข กและการกระจายสินค้า - ก (ข+ ค) = ก ข + ก กับ.

สำหรับแต่ละองค์ประกอบฟิลด์ กจะต้องมีองค์ประกอบผกผันที่จะบวก (-ก)และถ้า กไม่เท่ากับศูนย์ องค์ประกอบผกผันของการคูณ (th')

ฟิลด์จะต้องมี หน่วยเติมแต่ง -องค์ประกอบ 0 เช่นนั้น ก + 0 = กสำหรับองค์ประกอบฟิลด์ใดๆ ก.

ฟิลด์จะต้องมี หน่วยคูณ -องค์ประกอบที่ 1 เช่นนั้น อัล = กสำหรับองค์ประกอบฟิลด์ใดๆ ก.

ตัวอย่างเช่น มีช่องจำนวนจริง จำนวนตรรกยะ และจำนวนเชิงซ้อน ฟิลด์เหล่านี้มีองค์ประกอบจำนวนอนันต์

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

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

ในรหัสวงจร คำรหัสจะแสดงด้วยพหุนาม (พหุนาม)

ที่ไหน พี -ความยาวรหัส ฉัน -ค่าสัมประสิทธิ์ของฟิลด์ Galois (ค่าการรวมรหัส)

ตัวอย่างเช่น สำหรับชุดโค้ด 101101 รายการพหุนามจะมีรูปแบบ

ตัวอย่างของรหัสแบบวน ได้แก่ รหัสตรวจสอบคู่, รหัสซ้ำ, รหัส Hamming, รหัส PC และรหัสเทอร์โบ

รหัสแฮมมิง- ความสามารถในการแก้ไขข้อผิดพลาดในโค้ด Hamming นั้นสัมพันธ์กับระยะห่างของโค้ดขั้นต่ำ ง0ข้อผิดพลาดหลายหลากทั้งหมดได้รับการแก้ไขแล้ว ถาม= ซีเอ็นที (วัน 0- l)/2 (ในที่นี้ cnt หมายถึง "ส่วนจำนวนเต็ม") และตรวจพบข้อผิดพลาดหลายหลาก วัน 0 - 1. ดังนั้น เมื่อตรวจสอบความเท่าเทียมกันของเลขคี่ ง ถาม =ตรวจพบข้อผิดพลาด 2 รายการและข้อผิดพลาดเดียว ในรหัสแฮมมิง วัน 0 = 3. นอกจากหมวดหมู่ข้อมูลแล้ว ยังมีการแนะนำอีกด้วย ล=บันทึก 2 Q ของบิตควบคุมส่วนเกิน โดยที่ ถาม-จำนวนบิตข้อมูล พารามิเตอร์ ลปัดเศษให้เป็นค่าจำนวนเต็มที่สูงกว่าที่ใกล้ที่สุด รหัสควบคุม L-bit เป็นผลลัพธ์แบบกลับหัวของการบวกระดับบิต (เพิ่มเติมแบบโมดูโล 2) ของตัวเลขของบิตข้อมูลเหล่านั้นที่มีค่าเท่ากับหนึ่ง

ตัวอย่างที่ 7.7

ให้เรามีรหัสหลัก 100110 เช่น ถาม= 6. มากำหนดโค้ดเพิ่มเติมกัน

สารละลาย

เราพบว่า ล= 3 และโค้ดเสริมคือ

โดยที่ P เป็นสัญลักษณ์ของการดำเนินการบวกระดับบิต และหลังจากการผกผันเรามี 000 ตอนนี้รหัสเพิ่มเติมจะถูกส่งไปพร้อมกับรหัสหลัก ที่ผู้รับรหัสเพิ่มเติมจะถูกคำนวณอีกครั้งและเปรียบเทียบกับรหัสที่ส่ง รหัสเปรียบเทียบจะถูกบันทึก และหากแตกต่างจากศูนย์ ค่าของมันจะเป็นจำนวนบิตของรหัสหลักที่ได้รับอย่างผิดพลาด ดังนั้นหากยอมรับรหัส 100010 รหัสเพิ่มเติมที่คำนวณได้จะเท่ากับค่าผกผันของ010Ш10 = 100 นั่นคือ 011 ซึ่งหมายถึงข้อผิดพลาดในหลักที่ 3

ลักษณะทั่วไปของรหัส Hamming คือรหัส BCH แบบวนรอบ ซึ่งทำให้สามารถแก้ไขข้อผิดพลาดหลายข้อในชุดรหัสที่นำมาใช้ได้

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

รหัสเทอร์โบรหัสซ้ำซ้อนสามารถใช้ได้อย่างอิสระหรือในรูปแบบของการรวมกันของรหัสหลายรหัส เมื่อชุดสัญลักษณ์ของรหัสซ้ำซ้อนหนึ่งถูกพิจารณาว่าเป็นสัญลักษณ์ข้อมูลเบื้องต้นของรหัสซ้ำซ้อนอื่น สมาคมนี้จึงได้ชื่อว่า เรียงซ้อนรหัส. ข้อได้เปรียบอย่างมากของรหัสที่ต่อกันคือการใช้งานทำให้สามารถลดความซับซ้อนของตัวเข้ารหัสและโดยเฉพาะอย่างยิ่งตัวถอดรหัสเมื่อเปรียบเทียบกับอุปกรณ์ที่คล้ายกันซึ่งมีรหัสที่ไม่ต่อกันซึ่งมีความยาวและความซ้ำซ้อนเท่ากัน การเข้ารหัสแบบเรียงซ้อนนำไปสู่การสร้างรหัสเทอร์โบ รหัสเทอร์โบเรียกโครงสร้างสัญญาณแบบขนานที่ประกอบด้วยรหัสระบบตั้งแต่สองตัวขึ้นไป หลักการพื้นฐานของการก่อสร้างคือการใช้ตัวเข้ารหัสส่วนประกอบการทำงานแบบขนานหลายตัว คุณสามารถใช้ทั้งรหัสบล็อกและรหัส Convolutional รหัส Hamming รหัส PC BCH ฯลฯ การใช้การเจาะ (การเจาะ) ช่วยให้คุณสามารถเพิ่มความเร็วสัมพัทธ์ของรหัสเทอร์โบโดยปรับความสามารถในการแก้ไขให้เข้ากับลักษณะทางสถิติ ของช่องทางการสื่อสาร หลักการสร้างรหัสเทอร์โบมีดังนี้: สัญญาณอินพุต เอ็กซ์,ประกอบด้วย ถึงบิตเลี้ยงขนานไปกับ เอ็นผู้แทรกแซง แต่ละอันหลังเป็นอุปกรณ์ที่จัดเรียงองค์ประกอบในบล็อกของ ถึงบิตตามลำดับแบบสุ่มหลอก สัญญาณเอาท์พุตจากอินเทอร์ลีเวอร์ - สัญลักษณ์ที่มีลำดับการเปลี่ยนแปลง - จะถูกส่งไปยังตัวเข้ารหัสพื้นฐานที่เกี่ยวข้อง ลำดับไบนารี x พี ฉัน= 1,2,..., JV ที่เอาต์พุตของตัวเข้ารหัสคือสัญลักษณ์ตรวจสอบ ซึ่งเมื่อรวมกับบิตข้อมูลแล้ว จะทำให้เกิดเป็นโค้ดเวิร์ดคำเดียว การใช้อินเทอร์ลีเวอร์ทำให้สามารถป้องกันการเกิดลำดับของข้อผิดพลาดที่สัมพันธ์กันเมื่อถอดรหัสรหัสเทอร์โบ ซึ่งมีความสำคัญเมื่อใช้วิธีการถอดรหัสที่เกิดซ้ำแบบดั้งเดิมในการประมวลผล รหัสเทอร์โบแบ่งออกเป็นรหัสเทอร์โบแบบหมุนวนและรหัสผลิตภัณฑ์บล็อก ทั้งนี้ขึ้นอยู่กับการเลือกรหัสส่วนประกอบ

โค้ดแบบวนเป็นโค้ดเชิงเส้น ซึ่งเป็นเซตจำกัดที่ถูกปิดภายใต้การดำเนินการของการเปลี่ยนแปลงแบบวนของเวกเตอร์โค้ดที่ก่อตัวเป็นโค้ดนั้น ให้มันได้รับ 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. การคูณพหุนามสองตัวนี้

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

สิ่งนี้ช่วยให้เราสามารถพิจารณาเซตของคำที่มีความยาว n บนสนามจำกัดเป็นปริภูมิเชิงเส้นของพหุนามที่มีดีกรีมากที่สุด n-1 เหนือสนาม

คำอธิบายเกี่ยวกับพีชคณิต

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

โดยใช้ประโยชน์จากความจริงที่ว่า

เลื่อนไปทางขวาและซ้ายตามลำดับโดย เจอันดับ:

ถ้า ม(x) - พหุนามตามอำเภอใจเหนือสนาม ชเอฟ(ถาม) และ ค(x) - รหัสคำของวัฏจักร ( n,เค) จากนั้น ม(x)ค(x)มโอง(x n − 1) ยังเป็นคำรหัสสำหรับรหัสนี้

กำลังสร้างพหุนาม

คำนิยามพหุนามการสร้างของวงจร ( n,เค) รหัส คพหุนามที่ไม่เป็นศูนย์เช่นนี้เรียกว่า จาก คซึ่งมีดีกรีน้อยที่สุดและมีสัมประสิทธิ์ดีกรีสูงสุด ก ร = 1 .

ทฤษฎีบท 1

ถ้า ค- วงจร ( n,เค) รหัสและ ก(x) คือพหุนามกำเนิดของมัน ตามด้วยดีกรี ก(x) เท่ากับ ร = n − เค และแต่ละคำรหัสสามารถแสดงได้ไม่ซ้ำกันในแบบฟอร์ม

ค(x) = ม(x)ก(x) ,

ปริญญาอยู่ที่ไหน ม(x) น้อยกว่าหรือเท่ากับ เค − 1 .

ทฤษฎีบท 2

ก(x) - การสร้างพหุนามของวงจร ( n,เค) รหัสเป็นตัวหารของทวินาม x n − 1

ผลที่ตามมา:ด้วยเหตุนี้ พหุนามหรือตัวหารใดๆ จึงสามารถเลือกเป็นพหุนามสร้างได้ x n− 1 . ระดับของพหุนามที่เลือกจะกำหนดจำนวนสัญลักษณ์ทดสอบ ร, จำนวนสัญลักษณ์ข้อมูล เค = n − ร .

เมทริกซ์เครื่องกำเนิด

พหุนามมีความเป็นอิสระเชิงเส้น มิฉะนั้น ม(x)ก(x) = 0 สำหรับค่าที่ไม่ใช่ศูนย์ ม(x) ซึ่งเป็นไปไม่ได้

ซึ่งหมายความว่าสามารถเขียนโค้ดเวิร์ดได้สำหรับโค้ดเชิงเส้นดังนี้:

, ที่ไหน ชเป็น การสร้างเมทริกซ์, ม(x) - ข้อมูลพหุนาม

เมทริกซ์ ชสามารถเขียนเป็นสัญลักษณ์ได้ดังนี้

ตรวจสอบเมทริกซ์

สำหรับแต่ละรหัสของรหัสวงจร . นั่นเป็นเหตุผล ตรวจสอบเมทริกซ์สามารถเขียนเป็น:

การเข้ารหัส

ไม่เป็นระบบ

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

ค(x) = ม(x)ก(x) .

สามารถนำไปใช้ได้โดยใช้ตัวคูณพหุนาม

อย่างเป็นระบบ

ด้วยการเข้ารหัสอย่างเป็นระบบ คำรหัสจะถูกสร้างขึ้นในรูปแบบของบล็อกย่อยข้อมูลและการตรวจสอบ

ให้คำข้อมูลสร้างพลังที่สูงกว่าของคำรหัสแล้ว

ค(x) = x ร ม(x) + ส(x),ร = n − เค

แล้วจากเงื่อนไขเป็นไปตามนั้น

สมการนี้กำหนดกฎสำหรับการเข้ารหัสอย่างเป็นระบบ สามารถนำไปใช้ได้โดยใช้ตัวกรองเชิงเส้นหลายรอบ (MLF)

ตัวอย่าง

รหัสไบนารี่ (7,4,3)

เป็นตัวแบ่ง x 7 − 1 เราเลือกพหุนามกำเนิดของดีกรีที่สาม ก(x) = x 3 + x + 1 จากนั้นโค้ดที่ได้จะมีความยาว n= 7 จำนวนสัญลักษณ์ทดสอบ (ระดับการสร้างพหุนาม) ร= 3 จำนวนสัญลักษณ์ข้อมูล เค= 4 ระยะทางต่ำสุด ง = 3 .

เมทริกซ์เครื่องกำเนิดรหัส:

,

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

ตรวจสอบเมทริกซ์:

,

โดยที่คอลัมน์ที่ i ซึ่งเริ่มต้นจาก 0 แสดงถึงส่วนที่เหลือของการหาร x ฉันเป็นพหุนาม ก(x) เขียนโดยเรียงจากน้อยไปหามากโดยเริ่มจากด้านบน

ตัวอย่างเช่น ได้รับคอลัมน์ที่ 3 หรือในรูปแบบเวกเตอร์

มันง่ายที่จะตรวจสอบสิ่งนั้น ชชม ต = 0 .

รหัสไบนารี่ (15,7,5) BCH

เป็นพหุนามกำเนิด ก(x) คุณสามารถเลือกผลคูณของตัวหารสองตัวได้ x 15 − 1 ^

ก(x) = ก 1 (x)ก 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

จากนั้นแต่ละโค้ดเวิร์ดสามารถรับได้โดยใช้ผลคูณของพหุนามข้อมูล ม(x) มีวุฒิการศึกษา เค− 1 ดังนี้:

ค(x) = ม(x)ก(x) .

ตัวอย่างเช่น คำข้อมูลสอดคล้องกับพหุนาม ม(x) = x 6 + x 5 + x 4 + 1 แล้วตามด้วยรหัสคำ ค(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 หรือในรูปแบบเวกเตอร์

ดูเพิ่มเติม

ลิงค์

มูลนิธิวิกิมีเดีย

• 2010.
• รูปแบบวงจรในดนตรี

เงื่อนไขขอบเขตวงจร

ดูว่า "รหัส Cyclic" ในพจนานุกรมอื่นๆ คืออะไร:รหัสวงจรสั้นลง

- - [แอล.จี. ซูเมนโก พจนานุกรมภาษาอังกฤษเป็นภาษารัสเซียเกี่ยวกับเทคโนโลยีสารสนเทศ อ.: รัฐวิสาหกิจ TsNIIS, 2546.] หัวข้อเทคโนโลยีสารสนเทศโดยทั่วไป EN รหัสวงจรสั้นลง ...รหัสรีด-โซโลมอน

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

คู่มือนักแปลด้านเทคนิค

ข้อผิดพลาดในการแก้ไขรหัสรหัสแก้ไขข้อผิดพลาด

- การตรวจจับข้อผิดพลาดในเทคโนโลยีการสื่อสาร การดำเนินการที่มุ่งตรวจสอบความสมบูรณ์ของข้อมูล เมื่อบันทึก/ทำซ้ำข้อมูล หรือเมื่อส่งข้อมูลผ่านสายการสื่อสาร ขั้นตอนการแก้ไขข้อผิดพลาด (error Correction) ขั้นตอนการกู้คืนข้อมูลหลัง... ... Wikipediaรหัสแก้ไขข้อผิดพลาด