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

กราฟ Tanner ได้รับการเสนอโดย Michael Tanner ^{[ 1 ]}เป็นวิธีการสร้างรหัสแก้ไขข้อผิดพลาดขนาดใหญ่ขึ้นจากรหัสขนาดเล็กโดยใช้เทคนิคแบบเรียกซ้ำ เขาได้ขยายเทคนิคของPeter Eliasสำหรับรหัสผลิตภัณฑ์

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

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

แทนเนอร์ได้พิสูจน์ขอบเขตต่อไปนี้

ให้เป็นอัตราของรหัสเชิงเส้นที่ได้ ให้ เป็นดีกรีของโหนดตัวเลขและ เป็นดีกรีของโหนดรหัสย่อยถ้าแต่ละโหนดรหัสย่อยเชื่อมโยงกับรหัสเชิงเส้น ( n , k ) ที่มีอัตราr = k / nแล้ว อัตราของรหัสจะถูกจำกัดด้วย ${\displaystyle R}$${\displaystyle m}$${\displaystyle n}$

${\displaystyle R\geq 1-(1-r)m\,}$

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

อัลกอริทึมการถอดรหัสของ Zemorซึ่งเป็นวิธีการสร้างรหัสแบบเรียกซ้ำที่มีความซับซ้อนต่ำนั้น อิงตามกราฟ Tanner

• เอกสารต้นฉบับของไมเคิล แทนเนอร์
• หน้าของไมเคิล แทนเนอร์