รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ ( LDPC ) หรือที่รู้จักกันในชื่อรหัส Gallager เป็น รหัสแก้ไขข้อผิดพลาดประเภทหนึ่งที่เสนอครั้งแรกในปี 1960 ร่วมกับรหัสเทอร์โบ ที่เกี่ยวข้องอย่างใกล้ชิด รหัส เหล่านี้ได้รับความสำคัญในทฤษฎีการเข้ารหัสและทฤษฎีสารสนเทศตั้งแต่ปลายทศวรรษ 1990 ปัจจุบันรหัสเหล่านี้ถูกนำไปใช้อย่างกว้างขวางในแอปพลิเคชันต่างๆ ตั้งแต่การสื่อสารไร้สายไปจนถึงการจัดเก็บข้อมูลหน่วยความจำแฟลช ร่วมกับรหัสเทอร์โบ รหัสเหล่านี้ได้ก่อให้เกิดการปฏิวัติในทฤษฎีการเข้ารหัส ทำให้ประสิทธิภาพดีขึ้นหลายเท่าเมื่อเทียบกับรหัสแก้ไขข้อผิดพลาดแบบดั้งเดิม^{[ 1 ]}

รหัส LDPC ได้รับการคิดค้นขึ้นครั้งแรกโดยRobert G. Gallagerในปี 1960 Gallager ได้คิดค้นรหัสเหล่านี้ในวิทยานิพนธ์ระดับปริญญาเอกของเขา^{[ 2 ]}ที่สถาบันเทคโนโลยีแมสซาชูเซตส์ [ ^{3 ] [ 4 ] รหัส}เหล่านี้ถูกละเลยเป็นส่วนใหญ่ในขณะนั้น เนื่องจากอัลกอริทึมการถอดรหัสแบบวนซ้ำ (แม้จะมีความซับซ้อนเชิงเส้น) มีค่าใช้จ่ายในการคำนวณสูงเกินไปสำหรับฮาร์ดแวร์ที่มีอยู่ พวกมันกลับมาได้รับความนิยมอีกครั้งในช่วงกลางทศวรรษ 1990 ทั้งเพราะฮาร์ดแวร์ที่ได้รับการปรับปรุงทำให้ใช้งานได้จริง และเพราะพวกมันเป็นทางเลือกที่มีประสิทธิภาพสูงและปราศจากสิทธิบัตรแทนรหัสเทอร์โบ

หัวใจสำคัญของประสิทธิภาพของรหัส LDPC คือความสามารถในการปรับตัวให้เข้ากับ อัลกอริธึมการถอดรหัสการแพร่ กระจายความเชื่อแบบ วนซ้ำ ภายใต้อัลกอริธึมนี้ รหัสเหล่านี้สามารถออกแบบให้เข้าใกล้ขีดจำกัดทางทฤษฎี ( ความจุ ) ของช่องสัญญาณจำนวนมาก^{[ 5 ]}ด้วยต้นทุนการคำนวณที่ต่ำ

ความสนใจในรหัส LDPC กลับมาอีกครั้งหลังจากมีการคิดค้นรหัสเทอร์โบ ที่เกี่ยวข้องอย่างใกล้ชิด (1993) ซึ่งอัลกอริทึมการถอดรหัสแบบวนซ้ำที่คล้ายกันนั้นมีประสิทธิภาพเหนือกว่ารหัสอื่นๆ ที่ใช้ในเวลานั้น ต่อมารหัส LDPC ก็ถูกค้นพบอีกครั้งในปี 1996 ^{[ 6 ]} ความนิยมเริ่มต้นของอุตสาหกรรมสำหรับรหัส LDPC มากกว่ารหัสเทอร์โบนั้นเกิดจากข้อจำกัดที่เกี่ยวข้องกับสิทธิบัตรของ รหัสเทอร์โบ ^{[ 7 ]} นับตั้งแต่การค้นพบ ความก้าวหน้าในรหัส LDPC ทำให้มีประสิทธิภาพเหนือกว่ารหัสเทอร์โบในแง่ของ ค่าต่ำสุดของ ข้อผิดพลาดและประสิทธิภาพใน ช่วง อัตราการเข้ารหัส ที่สูงขึ้น ทำให้รหัสเทอร์โบเหมาะสมกว่าสำหรับอัตราการเข้ารหัสที่ต่ำกว่า^{[ 8 ]} แม้ว่าสิทธิบัตรพื้นฐานสำหรับรหัสเทอร์โบจะหมดอายุในปี 2013 ^{[ 9 ] [ 10 ]}แต่ในหลายกรณี รหัส LDPC ก็ยังคงเป็นที่นิยมมากกว่าเนื่องจากคุณสมบัติทางเทคนิค

ความสนใจเชิงทฤษฎีในรหัส LDPC ยังสืบเนื่องมาจากความเหมาะสมในการวิเคราะห์ทางคณิตศาสตร์ ในวิทยานิพนธ์ของเขา Gallager แสดงให้เห็นว่ารหัส LDPC บรรลุขอบเขต Gilbert–Varshamov สำหรับรหัสเชิงเส้นบนฟิลด์ไบนารีด้วยความน่าจะเป็นสูง บนช่องสัญญาณลบไบนารีลำดับรหัสได้รับการออกแบบที่อัตราที่ใกล้เคียงกับความจุของช่องสัญญาณอย่างไม่จำกัด โดยมีความน่าจะเป็นของข้อผิดพลาดในการถอดรหัสที่พิสูจน์ได้ว่าหายไปและความซับซ้อนในการถอดรหัสเชิงเส้น^{[ 11 ]} ในปี 2020 ได้มีการแสดงให้เห็นว่ารหัส LDPC ของ Gallager บรรลุ ความจุ ในการถอดรหัสรายการและยังบรรลุขอบเขต Gilbert–Varshamov สำหรับรหัสเชิงเส้นบนฟิลด์ทั่วไป อีกด้วย ^{[ 12 ]}

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

ประสิทธิภาพเชิงทฤษฎีนี้เกิดขึ้นได้โดยใช้การออกแบบที่ยืดหยุ่นซึ่งอิงตามกราฟ Tanner แบบเบาบาง ( กราฟสองส่วน เฉพาะ ) ^{[ 13 ]}

กลุ่มรหัส LDPC ยังได้รับการวิเคราะห์โดยใช้วิธีการจากฟิสิกส์เชิงสถิติ Murayama, Kabashima, Saad และ Vicente ศึกษารหัส LDPC ปกติผ่านการเปรียบเทียบระบบสปินและวิธีการจำลอง^{[ 14 ]}และงานในภายหลังได้ขยายการวิเคราะห์นี้ไปยังรหัส LDPC บนฟิลด์ Galois ^{[ 15 ]}

ตั้งแต่ปี 2013 รหัส LDPC ยังได้รับการเสนอให้เป็นวิธีการแก้ไขข้อผิดพลาดในคอมพิวเตอร์ควอนตัม เนื่องจากต้องการคิวบิตเพิ่มเติมเพียงเล็กน้อยในการแก้ไขข้อผิดพลาด ดังที่GottesmanมหาวิทยาลัยStrasburg Alice & Bob และอื่นๆ ได้แสดงให้เห็น ^{[ 16 ] [ 17 ] [ 18 ] [ 19 ]}การศึกษาในปี 2025 รายงาน รหัสควอน ตัม LDPC-CSSสำหรับช่องสัญญาณควอนตัมแบบดีโพลาไร ซ์ ซึ่งประสิทธิภาพการถอดรหัสเชิงตัวเลขเข้าใกล้ขีดจำกัดแฮชชิงในขณะที่ยังคงความซับซ้อนในการถอดรหัสเชิงเส้นตามจำนวนคิวบิตทางกายภาพ^{[ 20 ]}

ในปี พ.ศ. 2546 รหัส LDPC แบบ สะสมซ้ำไม่สม่ำเสมอ (IRA) เอาชนะรหัสเทอร์โบหกตัวเพื่อกลายเป็นรหัสแก้ไขข้อผิดพลาดใน มาตรฐาน DVB-S2 ใหม่ สำหรับโทรทัศน์ดิจิทัล^{[ 21 ]}การตัดสินใจนี้ขึ้นอยู่กับปัจจัยทางเทคนิค เช่น ความง่ายในการประมวลผลแบบขนานและระดับข้อผิดพลาด^{[ 22 ]}รวมถึงสถานะปลอดสิทธิบัตรของ LDPC ^{[ 23 ]}

ในปี พ.ศ. 2551 LDPC เอาชนะรหัสเทอร์โบแบบคอนโวลูชันในฐานะ ระบบ แก้ไขข้อผิดพลาดล่วงหน้า (FEC) สำหรับมาตรฐานITU-T G.hn ^{[ 24 ]} G.hn เลือกใช้รหัส LDPC แทนรหัสเทอร์โบเนื่องจากมีความซับซ้อนในการถอดรหัสต่ำกว่า (โดยเฉพาะเมื่อทำงานที่อัตราข้อมูลใกล้เคียง 1.0 Gbit/s) และเนื่องจากรหัสเทอร์โบที่เสนอมีระดับข้อผิดพลาดต่ำ อย่างมีนัยสำคัญ ในช่วงการทำงานที่ต้องการ^{[ 25 ]}

รหัส LDPC ยังใช้สำหรับ อีเธอร์เน็ต 10GBASE-Tซึ่งส่งข้อมูลที่ความเร็ว 10 กิกะบิตต่อวินาทีผ่านสายเคเบิลแบบบิดเกลียว ตั้งแต่ปี 2009 รหัส LDPC ยังเป็นส่วนหนึ่งของ มาตรฐาน Wi-Fi 802.11 ในฐานะส่วนเสริมของ802.11nและ802.11acในข้อกำหนด High Throughput (HT) PHY ^{[ 26 ]} LDPC เป็นส่วนบังคับของ802.11ax (Wi-Fi 6) ^{[ 27 ]}

ระบบ OFDMบางระบบเพิ่มการแก้ไขข้อผิดพลาดภายนอกเพิ่มเติมเพื่อแก้ไขข้อผิดพลาดเป็นครั้งคราว ("ระดับข้อผิดพลาด") ที่หลุดรอดจากการแก้ไขรหัสภายใน LDPC แม้จะมีอัตราข้อผิดพลาดบิต ต่ำก็ตาม ตัวอย่างเช่นรหัส Reed-Solomonที่ใช้การเข้ารหัสแบบ LDPC (RS-LCM) ใช้รหัสภายนอก Reed-Solomon ^{[ 28 ]}มาตรฐาน DVB-S2, DVB-T2 และ DVB-C2 ทั้งหมดใช้รหัสภายนอก BCHเพื่อกำจัดข้อผิดพลาดที่เหลืออยู่หลังจากการถอดรหัส LDPC ^{[ 29 ]}

5G NRใช้รหัสโพลาร์สำหรับช่องสัญญาณควบคุมและ LDPC สำหรับช่องสัญญาณข้อมูล^{[ 30 ] [ 31 ]}

แม้ว่ารหัส LDPC จะประสบความสำเร็จในฮาร์ดดิสก์ไดรฟ์เชิงพาณิชย์ แต่การใช้ประโยชน์จากความสามารถในการแก้ไขข้อผิดพลาดอย่างเต็มที่ในSSDจำเป็นต้องมีการตรวจจับหน่วยความจำแฟลชแบบละเอียดที่ไม่ธรรมดา ซึ่งนำไปสู่ความหน่วงแฝงในการอ่านหน่วยความจำที่เพิ่มขึ้น LDPC-in-SSD ^{[ 32 ]}เป็นแนวทางที่มีประสิทธิภาพในการใช้งาน LDPC ใน SSD โดยมีความหน่วงแฝงเพิ่มขึ้นเพียงเล็กน้อย ซึ่งทำให้ LDPC-in-SSD กลายเป็นความจริง ตั้งแต่นั้นมา LDPC ได้รับการนำไปใช้อย่างกว้างขวางใน SSD เชิงพาณิชย์ทั้งในระดับลูกค้าและระดับองค์กรโดยผู้จำหน่ายอุปกรณ์จัดเก็บข้อมูลรายใหญ่ SSD TLC (และรุ่นต่อมา) จำนวนมากใช้รหัส LDPC โดยจะพยายามถอดรหัสแบบฮาร์ดแวร์อย่างรวดเร็ว (การลบแบบไบนารี) ก่อน ซึ่งสามารถย้อนกลับไปใช้การถอดรหัสแบบซอฟต์แวร์ที่ช้ากว่าแต่มีประสิทธิภาพมากกว่าได้^{[ 33 ]}

รหัส LDPC ถูกกำหนดโดยฟังก์ชันด้วยเมทริกซ์ตรวจสอบความเท่าเทียม กันแบบเบาบาง เมทริกซ์แบบเบาบางนี้มักจะถูกสร้างขึ้นแบบสุ่ม โดยขึ้นอยู่กับข้อจำกัดของความเบาบาง— การสร้างรหัส LDPCจะกล่าวถึงในภายหลังรหัสเหล่านี้ได้รับการออกแบบครั้งแรกโดย Robert Gallager ในปี 1960 ^{[ 4 ]}

ด้านล่างนี้คือส่วนหนึ่งของกราฟตัวอย่างโค้ด LDPC ^{[ 34 ]}ที่ใช้สัญกรณ์กราฟปัจจัยของ Forneyในกราฟนี้ โหนดตัวแปร nโหนดที่ด้านบนของกราฟจะเชื่อมต่อกับโหนดข้อจำกัด ( n − k ) โหนดที่ด้านล่างของกราฟ

นี่เป็นวิธีการแสดงรหัส LDPC ( n ,  k ) ในรูปแบบกราฟิกที่นิยมใช้กัน บิตของข้อความที่ถูกต้อง เมื่อวางบนTที่ด้านบนของกราฟ จะเป็นไปตามข้อจำกัดของกราฟิก โดยเฉพาะอย่างยิ่ง เส้นทั้งหมดที่เชื่อมต่อกับโหนดตัวแปร (กล่องที่มีเครื่องหมาย "=") จะมีค่าเดียวกัน และค่าทั้งหมดที่เชื่อมต่อกับโหนดตัวประกอบ (กล่องที่มีเครื่องหมาย "+") จะต้องรวมกันได้ ศูนย์ เมื่อหารด้วยสอง (กล่าวคือ ผลรวมต้องเป็นเลขคู่ หรือต้องมีค่าคี่เป็นจำนวนคู่)

หากไม่นับเส้นที่อยู่นอกภาพ จะมีสตริงหกบิตที่เป็นไปได้แปดสตริงที่สอดคล้องกับคำรหัสที่ถูกต้อง: (เช่น 000000, 001110, 010111, 011001, 100101, 101011, 110010, 111100) ส่วนของรหัส LDPC นี้แสดงถึงข้อความสามบิตที่เข้ารหัสเป็นหกบิต การใช้ความซ้ำซ้อนในที่นี้เพื่อเพิ่มโอกาสในการกู้คืนจากข้อผิดพลาดของช่องสัญญาณ นี่คือรหัสเชิงเส้น (6, 3) โดยที่n  = 6 และk  = 3

โดยไม่นับเส้นที่อยู่นอกภาพ เมทริกซ์ตรวจสอบความเท่าเทียมกันที่แสดงถึงส่วนของกราฟนี้คือ

${\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}.}$

ในเมทริกซ์นี้ แต่ละแถวแสดงถึงข้อจำกัดการตรวจสอบความเท่าเทียมกันหนึ่งในสามข้อ ขณะที่แต่ละคอลัมน์แสดงถึงบิตหนึ่งในหกบิตในรหัสคำที่ได้รับ

ในตัวอย่างนี้ สามารถรับรหัสคำทั้งแปดคำได้โดยการนำเมทริกซ์ตรวจสอบความเท่าเทียมกันHมาใช้ในรูปแบบนี้ผ่านการดำเนินการแถว พื้นฐาน ในGF(2) : ${\displaystyle {\begin{bmatrix}-P^{T}|I_{nk}\end{bmatrix}}}$

${\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}_{1}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\0&1&1&0&1&0\\\end{pmatrix}}_{2}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\0&0&1&1&0&1\\\end{pmatrix}}_{3}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\\\end{pmatrix}}_{4}.}$

ขั้นตอนที่ 1: H.

ขั้นตอนที่ 2: นำแถวที่ 1 มาต่อกับแถวที่ 3

ขั้นตอนที่ 3: สลับแถวที่ 2 และ 3

ขั้นตอนที่ 4: นำแถวที่ 1 มาต่อกับแถวที่ 3

จากสิ่งนี้เมทริกซ์กำเนิดGสามารถหาได้ดังนี้(โดยสังเกตว่าในกรณีพิเศษที่เป็นรหัสไบนารี) หรือโดยเฉพาะเจาะจงคือ: ${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$${\displaystyle P=-P}$

${\displaystyle \mathbf {G} ={\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}.}$

สุดท้ายนี้ โดยการคูณสตริง 3 บิตที่เป็นไปได้ทั้งแปดแบบด้วยGจะได้รหัสคำที่ถูกต้องทั้งแปดแบบ ตัวอย่างเช่น รหัสคำสำหรับสตริงบิต "101" จะได้มาจากการคูณด้วย G

${\displaystyle {\begin{pmatrix}1&0&1\\\end{pmatrix}}\odot {\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}={\begin{pmatrix}1&0&1&0&1&1\\\end{pmatrix}}}$,

สัญลักษณ์ของการคูณแบบมอด 2 อยู่ ที่ไหน${\displaystyle \odot }$

เพื่อตรวจสอบความถูกต้อง ปริภูมิแถวของGตั้งฉากกับHโดยที่. ${\displaystyle G\odot H^{T}=0}$

สตริงบิตขาเข้า "101" พบว่าเป็น 3 บิตแรกของรหัสคำ "101011" เนื่องจากการมีอยู่ของเมทริกซ์เอกลักษณ์ส่วน 3 บิตสุดท้าย "011" ของรหัสคำนั้นคือบิตพาริตี ${\displaystyle I_{k}}$

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

ในระหว่างการเข้ารหัสเฟรม ข้อมูลบิตขาเข้า (D) จะถูกทำซ้ำและกระจายไปยังชุดของตัวเข้ารหัสย่อย ตัวเข้ารหัสย่อยเหล่านี้โดยทั่วไปจะเป็นตัวสะสม และตัวสะสมแต่ละตัวจะใช้ในการสร้างสัญลักษณ์พาริตี ข้อมูลต้นฉบับเพียงชุดเดียว (S _0,K-1 ) จะถูกส่งไปพร้อมกับบิตพาริตี (P) เพื่อสร้างสัญลักษณ์รหัส บิต S จากตัวเข้ารหัสย่อยแต่ละตัวจะถูกทิ้งไป

บิตพาริตีอาจถูกใช้ภายในรหัสส่วนประกอบอื่น ๆ

ในตัวอย่างการใช้ รหัสอัตรา DVB-S2 2/3 ขนาดบล็อกที่เข้ารหัสคือ 64800 สัญลักษณ์ (N=64800) โดยมีบิตข้อมูล 43200 บิต (K=43200) และบิตพาริตี 21600 บิต (M=21600) รหัสองค์ประกอบแต่ละรหัส (โหนดตรวจสอบ) เข้ารหัสบิตข้อมูล 16 บิต ยกเว้นบิตพาริตีแรกซึ่งเข้ารหัสบิตข้อมูล 8 บิต บิตข้อมูล 4680 บิตแรกจะถูกทำซ้ำ 13 ครั้ง (ใช้ในรหัสพาริตี 13 รหัส) ในขณะที่บิตข้อมูลที่เหลือจะถูกใช้ในรหัสพาริตี 3 รหัส (รหัส LDPC ที่ไม่ปกติ) ^{[ 35 ]}

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

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

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

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

เช่นเดียวกับรหัสอื่นๆการถอดรหัสความน่าจะเป็นสูงสุดของรหัส LDPC บนช่องสมมาตรไบนารีเป็นปัญหาNP-complete ^{[ 38 ]}ซึ่งแสดงให้เห็นโดยการลดจากการจับคู่แบบ 3 มิติดังนั้นสมมติว่าP != NPซึ่งเป็นที่เชื่อกันอย่างกว้างขวาง การดำเนินการถอดรหัสที่เหมาะสมที่สุดสำหรับรหัสใดๆ ที่มีขนาดที่ใช้งานได้จึงไม่ใช่เรื่องที่ทำได้จริง

อย่างไรก็ตาม เทคนิคที่ไม่เหมาะสมที่สุดซึ่งอิงกับ การถอดรหัส การแพร่กระจายความเชื่อ แบบวนซ้ำ ให้ผลลัพธ์ที่ยอดเยี่ยมและสามารถนำไปใช้ได้จริง เทคนิคการถอดรหัสที่ไม่เหมาะสมที่สุดจะมองการตรวจสอบความเท่าเทียมกันแต่ละครั้งที่ประกอบขึ้นเป็น LDPC เป็นรหัสตรวจสอบความเท่าเทียมกันเดี่ยว (SPC) ที่เป็นอิสระ รหัส SPC แต่ละรหัสจะถูกถอดรหัสแยกกันโดยใช้ เทคนิค soft-in-soft-out (SISO) เช่นSOVA , BCJR , MAPและเทคนิคอื่นๆ ที่พัฒนาต่อยอดจากเทคนิคเหล่านี้ ข้อมูลการตัดสินใจแบบอ่อนจากแต่ละการถอดรหัส SISO จะถูกตรวจสอบและอัปเดตด้วยการถอดรหัส SPC ที่ซ้ำซ้อนอื่นๆ ของบิตข้อมูลเดียวกัน จากนั้นรหัส SPC แต่ละรหัสจะถูกถอดรหัสอีกครั้งโดยใช้ข้อมูลการตัดสินใจแบบอ่อนที่อัปเดตแล้ว กระบวนการนี้จะทำซ้ำจนกว่าจะได้คำรหัสที่ถูกต้องหรือการถอดรหัสสิ้นสุดลง การถอดรหัสประเภทนี้มักเรียกว่าการถอดรหัสแบบผลรวม-ผลคูณ

การถอดรหัส SPC มักถูกเรียกว่ากระบวนการ "ตรวจสอบโหนด" และการตรวจสอบตัวแปรข้ามกันมักถูกเรียกว่ากระบวนการ "ตรวจสอบโหนดตัวแปร"

ในการใช้งานตัวถอดรหัส LDPC ในทางปฏิบัติ ชุดรหัส SPC จะถูกถอดรหัสแบบขนานเพื่อเพิ่มปริมาณงาน

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

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

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

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

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

สามารถตรวจสอบความถูกต้องของผลลัพธ์นี้ได้โดยการคูณรหัสคำที่แก้ไขแล้วrด้วยเมทริกซ์ตรวจสอบความเท่าเทียมกันH :

${\displaystyle \mathbf {z} =\mathbf {H\odot r} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}\odot {\begin{pmatrix}1\\0\\1\\0\\1\\1\\\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\\end{pmatrix}}.}$

เนื่องจากผลลัพธ์z ( ซินโดรม ) ของการดำเนินการนี้คือเวกเตอร์ศูนย์ขนาดสามคูณหนึ่ง ดังนั้นรหัสคำr ที่ได้ จึงได้รับการตรวจสอบความถูกต้องเรียบร้อยแล้ว

หลังจากถอดรหัสเสร็จแล้ว สามารถแยกบิตข้อความต้นฉบับ '101' ออกมาได้โดยพิจารณาจาก 3 บิตแรกของรหัสคำ

แม้ว่าตัวอย่างการลบนี้จะแสดงให้เห็นภาพรวม แต่ก็ไม่ได้แสดงให้เห็นถึงการใช้การถอดรหัสแบบตัดสินใจแบบอ่อน หรือการส่งข้อความแบบตัดสินใจแบบอ่อน ซึ่งใช้กันในตัวถอดรหัส LDPC เชิงพาณิชย์เกือบทั้งหมด

นับตั้งแต่ปี 2010 เป็นต้นมา มีการทำงานมากมายที่ศึกษาผลกระทบของตารางเวลาทางเลือกสำหรับการอัปเดตโหนดตัวแปรและโหนดข้อจำกัด เทคนิคดั้งเดิมที่ใช้ในการถอดรหัส LDPC เรียกว่าfloodingการอัปเดตประเภทนี้กำหนดให้ต้องอัปเดตโหนดข้อจำกัดทั้งหมดก่อนที่จะอัปเดตโหนดตัวแปร และในทางกลับกัน ในงานต่อมาโดย Vila Casado et al. [ ^{39 ] [ 40 ] ได้มีการศึกษาเทคนิคการอัปเดตทางเลือก ซึ่งโหนดตัวแปรจะได้รับการอัป เด}ตด้วยข้อมูลโหนดตรวจสอบล่าสุดที่มีอยู่

แนวคิดเบื้องหลังอัลกอริธึมเหล่านี้คือ โหนดตัวแปรที่มีค่าเปลี่ยนแปลงมากที่สุดคือโหนดที่ต้องได้รับการอัปเดตก่อน โหนดที่มีความน่าเชื่อถือสูง ซึ่งมีอัตราส่วนความน่าจะเป็นล็อก (LLR) ขนาดใหญ่และไม่เปลี่ยนแปลงอย่างมีนัยสำคัญจากการอัปเดตหนึ่งไปยังอีกการอัปเดตหนึ่ง ไม่จำเป็นต้องได้รับการอัปเดตด้วยความถี่เท่ากับโหนดอื่นๆ ที่มีเครื่องหมายและขนาดผันผวนมากกว่า^{[ 40 ]} อั ลกอริธึมการจัดตารางเวลาเหล่านี้แสดงให้เห็นถึงความเร็วในการบรรจบกันที่มากขึ้นและระดับข้อผิดพลาดที่ต่ำกว่าเมื่อเทียบกับอัลกอริธึมที่ใช้การแพร่กระจาย ระดับข้อผิดพลาดที่ต่ำกว่าเหล่านี้เกิดขึ้นได้จากความสามารถของอัลกอริธึมการจัดตารางเวลาแบบไดนามิกที่มีข้อมูล (IDS) ^{[ 39 ]}ในการเอาชนะชุดดักจับของรหัสคำใกล้เคียง^{[ 41 ]}

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

สำหรับขนาดบล็อกขนาดใหญ่ รหัส LDPC มักถูกสร้างขึ้นโดยการศึกษาพฤติกรรมของตัวถอดรหัสก่อน เมื่อขนาดบล็อกมีแนวโน้มเข้าสู่ค่าอนันต์ ตัวถอดรหัส LDPC จะแสดงให้เห็นว่ามีเกณฑ์สัญญาณรบกวนที่ต่ำกว่านั้นการถอดรหัสจะทำได้อย่างน่าเชื่อถือ และสูงกว่านั้นการถอดรหัสจะไม่สามารถทำได้^{[ 42 ]}ซึ่งเรียกกันทั่วไปว่าปรากฏการณ์หน้าผาเกณฑ์นี้สามารถปรับให้เหมาะสมที่สุดได้โดยการหาอัตราส่วนที่ดีที่สุดของส่วนโค้งจากโหนดตรวจสอบและส่วนโค้งจากโหนดตัวแปร วิธีการทางกราฟิกโดยประมาณในการแสดงภาพเกณฑ์นี้คือแผนภูมิEXIT ^{[ 43 ]}

การสร้างรหัส LDPC เฉพาะหลังจากการเพิ่มประสิทธิภาพนี้แบ่งออกเป็นสองประเภทหลัก ได้แก่^{[ 43 ]}

• วิธีการสุ่มเทียม
• แนวทางเชิงการจัดเรียง

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

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

รหัส LDPC บางรหัสมีพื้นฐานมาจากรหัส Reed–Solomonเช่น รหัส RS-LDPC ที่ใช้ในมาตรฐานอีเธอร์เน็ต 10 กิกะบิต^{[ 45 ]}เมื่อเปรียบเทียบกับรหัส LDPC ที่สร้างขึ้นแบบสุ่ม รหัส LDPC ที่มีโครงสร้าง เช่น รหัส LDPC ที่ใช้ใน มาตรฐาน DVB-S2สามารถใช้ฮาร์ดแวร์ที่เรียบง่ายกว่าและต้นทุนต่ำกว่าได้ โดยเฉพาะอย่างยิ่ง รหัสที่สร้างขึ้นเพื่อให้เมทริกซ์ H เป็น เมทริกซ์ แบบวงกลม^{[ 46 ]}

อีกวิธีหนึ่งในการสร้างรหัส LDPC คือการใช้เรขาคณิตจำกัดวิธีนี้ได้รับการเสนอโดย Y. Kou และคณะในปี 2001 ^{[ 47 ]}

รหัส LDPC สามารถเปรียบเทียบได้กับรูปแบบการเข้ารหัสที่มีประสิทธิภาพอื่นๆ เช่นรหัสเทอร์โบ^[ 48 ^]ในอีกด้านหนึ่ง ประสิทธิภาพ BERของรหัสเทอร์โบได้รับอิทธิพลจากข้อจำกัดของรหัสต่ำ^{[ 49 ] รหัส} LDPC ไม่มีข้อจำกัดของระยะทางขั้นต่ำ^{[ 50 ]}ซึ่งหมายความโดยอ้อมว่ารหัส LDPC อาจมีประสิทธิภาพมากกว่ารหัสเทอร์โบในอัตราการเข้ารหัส ที่ค่อนข้างสูง (เช่น 3/4, 5/6, 7/8) อย่างไรก็ตาม รหัส LDPC ไม่ใช่สิ่งทดแทนที่สมบูรณ์: รหัสเทอร์โบเป็นทางออกที่ดีที่สุดสำหรับอัตราการเข้ารหัสที่ต่ำกว่า (เช่น 1/6, 1/3, 1/2) ^{[ 36 ] [ 37 ]}

• ริชาร์ด แฮมมิง
• คลอดด์ แชนนอน
• เดวิด เจซี แม็คเคย์
• เออร์วิง เอส. รีด
• ไมเคิล ลูบี้

• ทฤษฎีกราฟ
• รหัสแฮมมิง
• รหัสกราฟแบบเบาบาง
• รหัสขยาย

• G.hn/G.9960 (มาตรฐาน ITU-T สำหรับการเชื่อมต่อเครือข่ายผ่านสายไฟ สายโทรศัพท์ และสายโคแอกเซียล)
• 802.3anหรือ 10GBASE-T (อีเธอร์เน็ต 10 กิกะบิต/วินาที ผ่านสายคู่บิดเกลียว)
• CMMB (การกระจายเสียงมัลติมีเดียเคลื่อนที่ของจีน)
• DVB-S2 / DVB-T2 / DVB-C2 (การออกอากาศวิดีโอดิจิทัล รุ่นที่ 2)
• DMB-T/H (การออกอากาศวิดีโอดิจิทัล) ^{[ 51 ]}
• WiMAX (มาตรฐาน IEEE 802.16e สำหรับการสื่อสารด้วยคลื่นไมโครเวฟ)
• IEEE 802.11n-2009 ( มาตรฐานWi-Fi )
• โดสซิส 3.1
• ATSC 3.0 (ระบบกระจายเสียงดิจิทัลภาคพื้นดินรุ่นใหม่สำหรับอเมริกาเหนือ)
• 3GPP (ช่องสัญญาณข้อมูล 5G-NR)

• รหัสน้ำพุ
• รหัส LT
• รหัสออนไลน์
• รหัสแรปเตอร์
• รหัสแบบทำซ้ำและสะสม (รหัสเทอร์โบแบบง่ายประเภทหนึ่ง)
• รหัสคอนโวลูชันแบบอนุกรมที่ต่อกัน
• รหัสทอร์นาโด (รหัส LDPC ที่ออกแบบมาสำหรับการถอดรหัสแบบลบข้อมูล )
• รหัสเทอร์โบ

จนถึงตอนนี้ มีเพียงความสามารถเดียวที่สามารถสร้างโค้ดโดยการออกแบบและพิสูจน์ได้

• รหัสขั้วโลก

• การแนะนำรหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ (โดย Sarah J Johnson, 2010)
• รหัส LDPC – บทช่วยสอนสั้น ๆ (โดย Bernhard Leiner, 2005)
• รหัส LDPC (TU Wien) เก็บถาวรเมื่อวันที่ 28 กุมภาพันธ์ 2019 ที่Wayback Machine
• MacKay, David JC (25 กันยายน 2546). "47. รหัสตรวจสอบความ เท่าเทียมกันความหนาแน่นต่ำ"ทฤษฎีสารสนเทศ การอนุมาน และอัลกอริธึมการเรียนรู้สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ หน้า  557–573 ISBN 978-0-521-64298-9.
• Guruswami, Venkatesan (2006). "การถอดรหัสแบบวนซ้ำของรหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ". arXiv : cs/0610022 .
• รหัส LDPC: บทนำ (โดย อามิน โชครอลลาฮี, 2003)
• การถอดรหัสการแพร่กระจายความเชื่อของรหัส LDPC (โดย อามีร์ เบนนาตัน, มหาวิทยาลัยพรินซ์ตัน)
• รหัส Turbo และ LDPC: การนำไปใช้ การจำลอง และการกำหนดมาตรฐาน (มหาวิทยาลัยเวสต์เวอร์จิเนีย)
• ทฤษฎีสารสนเทศและการเข้ารหัส (Marko Hennhöfer, 2011, TU Ilmenau) - กล่าวถึงรหัส LDPC ในหน้า 74–78
• รหัส LDPC และผลการปฏิบัติงาน
• การเชื่อมต่อ DVB-S.2 รวมถึงการเข้ารหัส LDPC (MatLab)
• ซอร์สโค้ดสำหรับการเข้ารหัส ถอดรหัส และจำลองรหัส LDPC สามารถดาวน์โหลดได้จากหลายแหล่ง:
  • รหัส LDPC ไบนารีในภาษาซี
  • โค้ด LDPC แบบไบนารีสำหรับPython (อัลกอริธึมหลักเขียนด้วยภาษา C)
  • ตัวเข้ารหัส LDPCและตัวถอดรหัส LDPCในMATLAB
  • เครื่องมือแก้ไขข้อผิดพลาดแบบเร่งด่วน (AFF3CT) ในภาษา C++11สำหรับการจำลอง LDPC อย่างรวดเร็ว