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

${\displaystyle C\subset \mathbb {F} _{2}^{n}}$ถือเป็นรหัสไบนารีที่มีความยาว; จะเป็นองค์ประกอบของ; และคือระยะห่างระหว่างองค์ประกอบเหล่านั้น ${\displaystyle n}$${\displaystyle x,y}$${\displaystyle \mathbb {F} _{2}^{n}}$${\displaystyle d(x,y)}$

อาจมีการส่งข้อความมาให้จากนั้นผู้สังเกตการณ์ในอุดมคติจะถอดรหัสและสร้างคำรหัสขึ้นมากระบวนการนี้จะส่งผลให้ได้คำตอบดังนี้: ${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

ตัวอย่างเช่น บุคคลสามารถเลือกคำรหัสที่น่าจะถูกรับเป็นข้อความหลังจากส่งได้ มากที่สุด${\displaystyle y}$${\displaystyle x}$

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

1. ขอให้ส่งรหัสคำอีกครั้ง – การส่งซ้ำอัตโนมัติ
2. เลือกคำรหัสใดก็ได้แบบสุ่มจากชุดคำรหัสที่มีความเป็นไปได้มากที่สุด ซึ่งใกล้เคียงกับคำรหัสนั้นมากที่สุด
3. หากมีรหัสอื่นตามมา ให้ทำเครื่องหมายส่วนที่ไม่ชัดเจนของรหัสคำเป็นส่วนที่ต้องลบออก และหวังว่ารหัสภายนอกจะช่วยขจัดความไม่ชัดเจนเหล่านั้นได้
4. แจ้งข้อผิดพลาดในการถอดรหัสไปยังระบบ

เมื่อได้รับเวกเตอร์แล้วการถอดรหัสแบบความน่าจะเป็นสูงสุดจะเลือกคำรหัสที่ทำให้ค่าสูงสุด${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (x{\mbox{ ได้รับ}}\mid y{\mbox{ ส่ง}})}$,

นั่นคือ รหัสคำที่เพิ่มความน่าจะเป็นสูงสุดในการได้รับ รหัส คำนั้น โดยกำหนดให้รหัสคำที่ส่งไปมีค่าเท่ากัน หากรหัสคำทุกคำมีโอกาสถูกส่งเท่ากัน วิธีการนี้จะเทียบเท่ากับการถอดรหัสโดยผู้สังเกตการณ์ในอุดมคติ อันที่จริง ตามทฤษฎีบทของเบย์ส ${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

${\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ ได้รับ}}\mid y{\mbox{ ส่ง}})&{}={\frac {\mathbb {P} (x{\mbox{ ได้รับ}},y{\mbox{ ส่ง}})}{\mathbb {P} (y{\mbox{ ส่ง}})}}\\&{}=\mathbb {P} (y{\mbox{ ส่ง}}\mid x{\mbox{ ได้รับ}})\cdot {\frac {\mathbb {P} (x{\mbox{ ได้รับ}})}{\mathbb {P} (y{\mbox{ ส่ง}})}}.\end{aligned}}}$

เมื่อกำหนดค่าคงที่แล้วค่าจะถูกปรับโครงสร้างใหม่และ คงที่ เนื่องจากรหัสคำทั้งหมดมีโอกาสถูกส่งเท่าๆ กัน ดังนั้น ค่า จะถูกทำให้สูงสุดในฐานะฟังก์ชันของตัวแปรก็ต่อเมื่อ ค่าถูกทำให้สูงสุด และข้ออ้างจึงเป็น จริง${\displaystyle \mathbb {P} (x{\mbox{ received}})}$${\displaystyle x}$${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$${\displaystyle y}$${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

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

ปัญหาการถอดรหัสความน่าจะเป็นสูงสุดยังสามารถจำลองเป็นปัญหาการเขียนโปรแกรมจำนวนเต็ม ได้อีกด้วย ^{[ 1 ]}

อัลกอริทึมการถอดรหัสความน่าจะเป็นสูงสุดเป็นตัวอย่างหนึ่งของปัญหา "การหาค่าเฉลี่ยของฟังก์ชันผลคูณ" ซึ่งแก้ไขโดยการใช้ กฎ การกระจายทั่วไป^{[ 2 ]}

เมื่อได้รับเวกเตอร์แล้วการถอดรหัสระยะทางต่ำสุดจะเลือกคำรหัสที่ทำให้ระยะทางแฮมมิง น้อยที่สุด : ${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle y\in C}$

${\displaystyle d(x,y)=|\{i:x_{i}\not =y_{i}\}|}$

เช่น เลือกคำรหัสที่ใกล้เคียงกับ มากที่สุด ${\displaystyle y}$${\displaystyle x}$

โปรดทราบว่า หากความน่าจะเป็นของข้อผิดพลาดบนช่องสัญญาณแบบไม่ต่อเนื่องที่ไม่มีหน่วยความจำ นั้นน้อยกว่าครึ่งหนึ่งอย่างเคร่งครัดการถอดรหัสระยะทางต่ำสุดจะเทียบเท่ากับการถอดรหัสความน่าจะเป็นสูงสุดเนื่องจากถ้า ${\displaystyle p}$

${\displaystyle d(x,y)=d,\,}$

แล้ว:

${\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

ซึ่ง (เนื่องจากpน้อยกว่าครึ่งหนึ่ง) จะมีค่าสูงสุดเมื่อลดค่าd ให้เหลือน้อย ที่สุด

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

1. โอกาสที่จะเกิดข้อผิดพลาดนั้นไม่ขึ้นอยู่กับตำแหน่งของสัญลักษณ์${\displaystyle p}$
2. ข้อผิดพลาดเป็นเหตุการณ์ที่เป็นอิสระต่อกัน – ข้อผิดพลาดในตำแหน่งหนึ่งของข้อความจะไม่ส่งผลกระทบต่อตำแหน่งอื่น ๆ

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

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

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

สมมติว่าเป็นรหัสเชิงเส้นที่มีความยาวและระยะห่างต่ำสุดพร้อมเมทริกซ์ตรวจสอบความเท่าเทียมกันแล้วเห็นได้ชัดว่าสามารถแก้ไขข้อผิดพลาดได้ถึง ${\displaystyle C\subset \mathbb {F} _{2}^{n}}$${\displaystyle n}$${\displaystyle d}$${\displaystyle H}$${\displaystyle C}$

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$

ข้อผิดพลาดที่เกิดจากช่องสัญญาณ (เนื่องจากหากไม่มีข้อผิดพลาดมากกว่านี้ การถอดรหัสระยะทางขั้นต่ำจะยังคงถอดรหัสคำรหัสที่ส่งมาผิดพลาดได้อย่างถูกต้อง) ${\displaystyle t}$

สมมติว่ามีการส่งรหัสคำผ่านช่องสัญญาณและเกิดรูปแบบข้อผิดพลาดขึ้น จากนั้นจึงได้รับเวกเตอร์ การถอดรหัสระยะทางต่ำสุดแบบปกติจะค้นหาเวกเตอร์ในตารางขนาดเพื่อหาค่าที่ตรงกันที่สุด กล่าวคือ องค์ประกอบ (ไม่จำเป็นต้องเป็นเอกลักษณ์) ที่มี ${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle e\in \mathbb {F} _{2}^{n}}$${\displaystyle z=x+e}$${\displaystyle z}$${\displaystyle |C|}$${\displaystyle c\in C}$

${\displaystyle d(c,z)\leq d(y,z)}$

สำหรับทุกคนการถอดรหัสซินโดรมใช้ประโยชน์จากคุณสมบัติของเมทริกซ์พาริตีที่ว่า: ${\displaystyle y\in C}$

${\displaystyle Hx=0}$

สำหรับทุกคนกลุ่มอาการที่ได้รับนั้นถูกกำหนดไว้ดังนี้: ${\displaystyle x\in C}$${\displaystyle z=x+e}$

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$

ในการถอดรหัส MLในช่องสัญญาณสมมาตรแบบไบนารีจำเป็นต้องค้นหาตารางที่คำนวณไว้ล่วงหน้าขนาด ซึ่งแมปไป ยัง${\displaystyle 2^{n-k}}$${\displaystyle He}$${\displaystyle e}$

โปรดทราบว่าวิธีการนี้มีความซับซ้อนน้อยกว่าการถอดรหัสอาร์เรย์แบบมาตรฐาน อย่างมาก แล้ว

อย่างไรก็ตาม ภายใต้สมมติฐานว่าไม่มีข้อผิดพลาดเกิดขึ้นระหว่างการส่งข้อมูล ผู้รับสามารถค้นหาค่าในตารางที่มีขนาดเล็กลงได้อีก ${\displaystyle t}$${\displaystyle He}$

${\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}$

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

รูปแบบที่ง่ายที่สุดมาจาก Prange: ให้เป็นเมทริกซ์กำเนิดที่ใช้สำหรับการเข้ารหัส เลือกคอลัมน์ของแบบสุ่ม และกำหนดให้ เป็นเมทริกซ์ย่อยที่สอดคล้องกันของด้วยความน่าจะเป็นที่เหมาะสมจะมีอันดับเต็ม ซึ่งหมายความว่า ถ้าเราให้เป็นเวกเตอร์ย่อยสำหรับตำแหน่งที่สอดคล้องกันของรหัสคำใดๆของสำหรับข้อความเราสามารถกู้คืนเป็น ได้ดังนั้น ถ้าเราโชคดีที่ตำแหน่งเหล่านี้ของคำที่ได้รับไม่มีข้อผิดพลาด และเท่ากับตำแหน่งของรหัสคำที่ส่งไป เราก็สามารถถอดรหัสได้ ${\displaystyle G}$${\displaystyle k\times n}$${\displaystyle C}$${\displaystyle k}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle c'}$${\displaystyle c=mG}$${\displaystyle C}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m=c'G'^{-1}}$${\displaystyle k}$${\displaystyle y}$

หากเกิดข้อผิดพลาด ความน่าจะเป็นของการเลือกคอลัมน์ที่ถูกต้องนั้นจะคำนวณได้จากสูตร. ${\displaystyle t}$${\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}$

วิธีการนี้ได้รับการปรับปรุงในหลายๆ ด้าน เช่น โดย Stern ^{[ 4 ]}และCanteautและ Sendrier ^{[ 5 ]}

วิธีการหา ค่าความน่าจะเป็นสูงสุดแบบตอบสนองบางส่วน ( PRML ) เป็นวิธีการแปลงสัญญาณอนาล็อกที่อ่อนจากหัวอ่านของดิสก์แม่เหล็กหรือไดรฟ์เทปให้เป็นสัญญาณดิจิทัล

ตัวถอดรหัส Viterbi ใช้ขั้นตอนวิธี Viterbiในการถอดรหัสบิตสตรีมที่ได้รับการเข้ารหัสโดยใช้การแก้ไขข้อผิดพลาดแบบส่งต่อ (Forward Error Correction)โดยอาศัย รหัสแบบคอนโว ลูชัน (Convolutional Code ) ระยะทางแฮมมิง (Hamming distance)ถูกใช้เป็นตัวชี้วัดสำหรับตัวถอดรหัส Viterbi แบบตัดสินใจอย่างเข้มงวด (Hard Decision Viterbi decoder) ส่วนระยะทางยูคลิดกำลังสอง (Squared Euclidean distance) ถูกใช้เป็นตัวชี้วัดสำหรับตัวถอดรหัสแบบตัดสินใจอย่างอ่อน (Soft Decision decoder)

อัลกอริธึมการถอดรหัส การตัดสินใจที่เหมาะสมที่สุด (ODDA) สำหรับระบบ TWRC แบบอสมมาตร^{[ 6 ]}

• ไม่สนใจสัญญาณเตือน
• การตรวจจับและแก้ไขข้อผิดพลาด
• ไม่อนุญาตให้ป้อนข้อมูล

• ฮิลล์, เรย์มอนด์ (1986). หลักสูตรเบื้องต้นเกี่ยวกับทฤษฎีการเข้ารหัส . ชุดคณิตศาสตร์ประยุกต์และวิทยาการคำนวณแห่งออกซ์ฟอร์ด. สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด . ISBN 978-0-19-853803-5.
• Pless, Vera (1982). บทนำสู่ทฤษฎีของรหัสแก้ไขข้อผิดพลาด . ชุดหนังสือคณิตศาสตร์เชิงดิสครีตของ Wiley-Interscience. John Wiley & Sons . ISBN 978-0-471-08684-0.
• van Lint, Jacobus H. (1992). บทนำสู่ทฤษฎีการเข้ารหัส . ตำราระดับบัณฑิตศึกษาทางคณิตศาสตร์ (GTM). เล่มที่ 86 (ฉบับที่ 2). Springer-Verlag . ISBN 978-3-540-54894-2.