รหัสแอลดีพีซี

รหัสพาริตีเช็กความหนาแน่นต่ำ (Low-Density Parity-Check Codes: LDPC) หรือที่นิยมเรียกโดยย่อว่า รหัสแอลดีพีซี จัดเป็นรหัสแก้ไขความผิดพลาดข้างหน้า (Forward Error Correcting Codes) ประเภทหนึ่งที่มีประสิทธิภาพสูงมาก เพราะสามารถให้สมรรถนะการแก้ไขความผิดพลาดที่เข้าใกล้ขีดจำกัดของแชนนอน (Shannon’s Limit) ได้ ซึ่งหมายความว่า ระบบสามารถใช้ประโยชน์จากช่องสัญญาณสื่อสารได้ถึงศักยภาพสูงสุดเท่าที่เป็นไปได้ รหัสแอลดีพีซีได้รับการคิดค้นขึ้นโดย Robert Gallager โดยเป็นส่วนหนึ่งของงานวิทยานิพนธ์ปริญญาเอกแห่งสถาบัน Massachusetts Institute of Technology (MIT) ใน พ.ศ. 1960

รูปที่ 1 Robert Gallager ผู้คิดค้นรหัสแอลดีพีซีในปี ค.ศ.1960
รูปที่ 2 Robert Gallager รับรางวัลผู้คิดค้นรหัสแอลดีพีซีจากองค์กร IEEE ในปี ค.ศ.1990

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

กระบวนการถอดรหัสเทอร์โบใช้หลักการทำงานแบบวนซ้ำ (Iterative Decoding) คล้ายคลึงกับรหัสแอลดีพีซี เป็นเหตุให้รหัสแอลดีพีซีได้รับความสนใจอีกครั้ง โดยใน ค.ศ. 1996 นักวิจัย David Mackay ได้นำรหัสแอลดีพีซีกลับมาวิจัยใหม่ ด้วยการนำเสนอวิธีการถอดรหัสวนซ้ำด้วยอัลกอริทึมการแพร่กระจายความเชื่อมั่น (Belief Propagation) และได้ทำการพิสูจน์ว่าสมรรถนะของรหัสแอลดีพีซีเข้าใกล้ขีดจำกัดของแชนนอน  เช่นเดียวกับรหัสเทอร์โบ โดยมีความซับซ้อนที่ต่ำกว่ารหัสเทอโบมาก ซึ่งผลการค้นคว้าวิจัยดังกล่าวจุด ประกายให้เกิดการพัฒนาและค้นพบรหัสแอลดีพีซีรูปแบบใหม่ ๆ ที่มีประสิทธิภาพดีขึ้นอย่างมาก 

รูปที่ 3 ผลการจำลองเพื่อแสดงให้เห็นว่าสมรรถนะของรหัสแอลดีพีซีเข้าใกล้ขีดจำกัดแชนนอน
รูปที่ 4 เมทริกซ์พาริตี้เช็ก H และกราฟแทนเนอร์

รายละเอียดเพิ่มเติม . . .

ในการเข้ารหัสแอลดีพีซีนั้น บิตข้อมูลที่ต้องการส่งจะถูกแบ่งออกเป็นบล็อกย่อย ๆ ที่มีความยาวเท่ากับ \(\displaystyle k\) บิต เท่า ๆ กัน ซึ่งบิตข้อมูลในแต่ละบล็อกจะอยู่ในรูปเวกเตอร์ \(\displaystyle \mathbf{u}=[{{u}_{0}},{{u}_{1}},{{u}_{2}}…..,{{u}_{{k-1}}}]\) และเมื่อนำเวกเตอร์บิตข้อมูลแต่ละบล็อกป้อนเข้าสู่วงจรเข้ารหัส จะเกิดเป็นบล็อกข้อมูลชุดใหม่ที่มีความยาวเพิ่มขึ้นเรียกว่า “คำรหัส (Codeword)” นิยามเป็นเวกเตอร์ \(\displaystyle \mathbf{c}=[{{c}_{0}},{{c}_{1}},{{c}_{2}}…..,{{c}_{{n-1}}}]\) มีความยาวเท่ากับ \(\displaystyle n\) บิตที่ถูกเพิ่มเข้ามาในคำรหัสจะถูกเรียกเรียกว่า “บิตพาริตี้ (Parity)” นิยามเป็นเวกเตอร์ \(\displaystyle \mathbf{b}=[{{b}_{0}},{{b}_{1}},{{b}_{2}}…..,{{b}_{{n-k}}}]\) มีความยาวเท่ากับ \(\displaystyle n – k\) เราสามารถคำนวณอัตรารหัสได้จาก

\(\displaystyle R=k/n\)

ในการเข้ารหัสบิตข้อมูลความยาว \(\displaystyle k\) ให้เกิดเป็นคำรหัสความยาว \(\displaystyle n\) นั้น ภายในวงจรเข้ารหัสแอลดีพีซี จะประกอบไปด้วยเมทริกซ์พาริตี้เช็ก \(\displaystyle \mathbf{H}\) ดังนี้

\(\displaystyle \mathbf{H}=\left[ {\begin{array}{*{20}{c}} {{{h}_{{11}}}} & {{{h}_{{12}}}} & \cdots & {{{h}_{{1j}}}} \\ {{{h}_{{21}}}} & {{{h}_{{22}}}} & \cdots & {{{h}_{{2j}}}} \\ \vdots & \vdots & \ddots & \vdots \\ {{{h}_{{i1}}}} & {{{h}_{{i2}}}} & \cdots & {{{h}_{{ij}}}} \end{array}} \right]\)

เมทริกซ์ \(\displaystyle \mathbf{H}\) มีไว้สำหรับสร้างคำรหัสจากบิตข้อมูลที่ถูกป้อนเข้ามา สมาชิกแต่ละตัวในเมทริกซ์ \(\displaystyle {{h}_{{ij}}}\) มีค่าเป็นได้ 2 แบบคือ 0 หรือ 1 คุณลักษณะสำคัญของรหัสแอลดีพีซีคือเมทริกซ์พาริตีเช็กคือมีเลข 1 จํานวนน้อยมากเมื่อเทียบกับขนาดเมทริกซ์ หรืออาจกล่าวได้ว่าเมทริกซ์มีความหนาแน่นตํ่า (sparse matrix) อย่างไรก็ตาม เพื่อให้การเข้ารหัสง่ายขึ้น เมทริกซ์ \(\displaystyle \mathbf{H}\) จะถูกนำไปทำ Gaussian elimination เพื่อแปลงสมาชิกแต่ละตัวในเมทริกซ์ให้อยู่ในรูป

\(\displaystyle \mathbf{H}=\left[ {\begin{array}{*{20}{c}} 1 & 0 & \cdots & 0 & {{{p}_{{00}}}} & {{{p}_{{10}}}} & \cdots & {{{p}_{{k-1,0}}}} \\ 0 & 1 & \cdots & 0 & {{{p}_{{01}}}} & {{{p}_{{11}}}} & \cdots & {{{p}_{{k-1,1}}}} \\ \vdots & \vdots & {} & \vdots & \vdots & \vdots & {} & \vdots \\ 0 & 0 & \cdots & 1 & {{{p}_{{0,n-k-1}}}} & {{{p}_{{1,n-k-1}}}} & \cdots & {{{p}_{{k-1,n-k-1}}}} \end{array}} \right]=\left[ {{{\mathbf{I}}_{{n-k}}}{{\mathbf{P}}^{\text{T}}}} \right]\)

โดยเมทริกซ์ \(\displaystyle {{\mathbf{P}}^{\text{T}}}\) คือทรานสโพตของเมทริกซ์ต้นกำเนิดบิตพาริตี้ย่อย การเข้ารหัสเวกเตอร์ \(\displaystyle \mathbf{u}\) กับเมทริกซ์ \(\displaystyle \mathbf{H}\) จะใช้ความสัมพันธ์ 

\(\displaystyle \mathbf{H}\bullet {{\mathbf{c}}^{\text{T}}}=\mathbf{H}\bullet \left[ {\begin{array}{*{20}{c}} \mathbf{b} \\ \mathbf{u} \end{array}} \right]=\mathbf{0}\)

โดย \(\displaystyle \mathbf{b}\) คือเวกเตอร์บิตพาริตี้ที่จะทำการค้นหา ซึ่งมีความยาวเท่ากับ \(\displaystyle n-k\) และ \(\displaystyle \mathbf{u}\) คือ เวกเตอร์ข้อมูล ฉะนั้น เมื่อทำการคูณกันระหว่างเมทริกซ์ทั้งสองตามความสัมพันธ์ที่กล่าวมาข้างต้นจะได้

\(\displaystyle \left[ {\begin{array}{*{20}{c}} {{{b}_{0}}} & 0 & \cdots & 0 & {{{u}_{0}}{{p}_{{00}}}} & {{{u}_{1}}{{p}_{{10}}}} & \cdots & {{{u}_{{k-1}}}{{p}_{{k-1,0}}}} \\ 0 & {{{b}_{1}}} & \cdots & 0 & {{{u}_{0}}{{p}_{{01}}}} & {{{u}_{1}}{{p}_{{11}}}} & \cdots & {{{u}_{{k-1}}}{{p}_{{k-1,1}}}} \\ \vdots & \vdots & {} & \vdots & \vdots & \vdots & {} & \vdots \\ 0 & 0 & \cdots & {{{b}_{{n-k-1}}}} & {{{u}_{0}}{{p}_{{0,n-k-1}}}} & {{{u}_{1}}{{p}_{{1,n-k-1}}}} & \cdots & {{{u}_{{k-1}}}{{p}_{{k-1,n-k-1}}}} \end{array}} \right]=\mathbf{0}\)

เราสามารถหาบิตพาริตี้แต่ละตัวได้จากสมการ

\(\displaystyle {{b}_{i}}={{u}_{0}}{{p}_{{0i}}}+{{u}_{1}}{{p}_{{1i}}}+……..+{{u}_{{k-1}}}{{p}_{{k-1,i}}}\)

โดย \(\displaystyle i=0,1,……,n-k-1\)  วิธีเข้ารหัสแอลดีพีซีโดยการนำเวกเตอร์บิตข้อมูลมาคูณกับเมทริกซ์ \(\displaystyle \mathbf{H}\) จะทำให้ได้เวกเตอร์คำรหัสที่เป็นรหัสเชิงระบบ (Systematic format) กล่าวคือ บิตข้อมูล และบิตพาริตี้จะถูกแยกออกจากกันอย่างชัดเจน

ดังที่ทราบกันดีแล้วว่า คำรหัสแอลดีพีซีถูกสร้างมาจากเมทริกซ์พาริตี้เช็ก \(\displaystyle \mathbf{H}\) อย่างไรก็ตาม เพื่อความง่ายในการพิจารณาความสัมพันธ์ของแต่ละบิตภายในคำรหัส (ไม่พิจารณาจาก \(\displaystyle \mathbf{H}\) อีกต่อไป) เราสามารถอธิบายความสัมพันธ์ของคำรหัสแอลดีพีซีในรูปกราฟสองส่วนหรือ “กราฟแทนเนอร์ (Tanner graph)” กล่าวคือ โนดในกราฟถูกแบ่งออกเป็น 2 ส่วนได้แก่ โนดบิต (Bit nodes) และโนดตรวจสอบ (Check nodes) สิ่งสำคัญคือโนดในกลุ่มในเดียวกันจะไม่มีการเชื่อมถึงกันแต่อย่างใด จะเห็นว่าลิงก์ในกราฟจะต่อเชื่อมเฉพาะระหว่างโนดบิตกับโนดตรวจสอบเท่านั้น ดูตัวอย่างกราฟแทนเนอร์ในรูปที่ 4 (ก) กราฟแทนเนอร์มีความสัมพันธ์โดยตรงกับเมทริกซ์ \(\displaystyle \mathbf{H}\) ดังนี้คือโนดบิตแต่ละโนดแทนคอลัมน์แต่ละคอลัมน์ในเมทริกซ์ \(\displaystyle \mathbf{H}\) และโนดตรวจสอบแต่ละโนดแทนแถวแต่ละแถวในเมทริกซ์ \(\displaystyle \mathbf{H}\) ทั้งนี้ โนดบิตในลำดับที่ \(\displaystyle j\) (หรือโนดบิต \(\displaystyle {{c}_{j}}\)) จะมีลิงก์เชื่อมต่อกับโนดตรวจสอบในลำดับที่ \(\displaystyle i\) (หรือ โนดตรวจสอบ \(\displaystyle {{f}_{i}}\)) ได้ก็ต่อเมื่อสมาชิก \(\displaystyle {{h}_{{ij}}}\) มีค่าเป็น 1 การแสดงรหัสแอลดีพีซีในรูปของกราฟแทนเนอร์เป็นประโยชน์ในการอธิบายถึงโครงสร้างและหลักการทำงานของรหัสแอลดีพีซีได้เป็นอย่างดี ตัวอย่างเช่น หากพิจารณาโนดตรวจสอบ \(\displaystyle {{f}_{1}}\) จะเห็นได้ทันทีว่ารหัสนี้กำหนดเงื่อนไขการตรวจสอบจากกระบวนการเขารหัสมาแล้วว่า

\(\displaystyle {{c}_{1}}+{{c}_{4}}+{{c}_{5}}+{{c}_{7}}=0\)

นั่นคือหากนำบิต \(\displaystyle {{c}_{1}}\),  \(\displaystyle {{c}_{4}}\), \(\displaystyle {{c}_{5}}\) และ \(\displaystyle {{c}_{7}}\) ของคำรหัสใด ๆ มาบวกกันแบบเลขฐาน 2 จะต้องมีค่าเป็น 0 เสมอ รหัสดังกล่าวนี้มีการกำหนดเงื่อนไขในลักษณะเดียวกันอีก 3 เงื่อนไข ซึ่งดูได้จากบิตตรวจสอบ \(\displaystyle {{f}_{2}}\), \(\displaystyle {{f}_{3}}\) และ \(\displaystyle {{f}_{4}}\) ของกราฟแทนเนอร์ นั่นคือ เงื่อนไขต่อไปนี้ต้องเป็นจริงเสมอสำหรับคำรหัสใด ๆ ของรหัส (8,4) ดังกล่าว

\(\displaystyle \begin{array}{l}{{c}_{2}}+{{c}_{4}}+{{c}_{6}}+{{c}_{7}}=0\\{{c}_{3}}+{{c}_{5}}+{{c}_{6}}+{{c}_{8}}=0\\{{c}_{2}}+{{c}_{3}}+{{c}_{4}}+{{c}_{8}}=0\end{array}\)

นอกจากนี้ กราฟแทนเนอร์ยังเป็นเครื่องมือสำหรับใช้ในการอธิบายกระบวนการถอดรหัสแบบวนซ้ำ โดยการกำหนดเงื่อนไขตรวจสอบข้างต้นสามารถใช้ตรวจจับและแก้ไขความผิดพลาดที่อาจเกิดขึ้นกับคำรหัสแอลดีพีซีได้ ยกตัวอย่างเช่น เมื่อบิต \(\displaystyle {{c}_{i}}\) เกิดความผิดพลาดจะทำให้ผลบวกของสมการที่มีความเกี่ยวข้องกับ \(\displaystyle {{c}_{i}}\) มีค่าเท่ากับ 1 ซึ่งขัดแย้งกับข้อกำหนดของรหัสในหลักการแล้วมีความหมายว่าภาครับสามารถใช้ผลการตรวจสอบดังกล่าวในการระบุตำแหน่งของบิตที่ผิดพลาดได้  

ภายหลังจากการเข้ารหัสแอลดีพีซีที่ภาคส่ง คำรหัส \(\displaystyle \mathbf{v}\) ที่ได้จะถูกมอดูเลตด้วยสัญญาณบีพีเอสเค (BPSK) เกิดเป็นสัญญาณเพื่อเตรียมส่ง \(\displaystyle \mathbf{x}\) โดยที่ \(\displaystyle \mathbf{x}=2\mathbf{v}-1\)  จากนั้น จะถูกส่งผ่านตัวกลางหรือช่องสัญญาณสื่อสาร ที่ประกอบไปด้วยสัญญาณรบกวนชนิดต่างๆ ซึ่งภาครับจะมีวงจรถอดรหัส ที่ทำหน้าที่ในการถอดรหัสสัญญาณที่ได้รับ \(\displaystyle \mathbf{y}\) โดยที่ \(\displaystyle \mathbf{y}=\mathbf{x}+\mathbf{n}\) เมื่อ \(\displaystyle \mathbf{n}\) คือสัญญาณรบกวน เพื่อกู้ข้อมูล จากภาคส่งกลับคืนมา  การถอดรหัสแอลดีพีซีจะอาศัยความสัมพันธ์และการเชื่อมต่อกันระหว่างโนดบิต และโนดเช็คบนกราฟแทนเนอร์ เป็นตัวกำหนดวิธีการ และขั้นตอนในการถอดรหัสแอลดีพีซี 

การถอดรหัสแอลดีพีซีที่ถูกใช้กันอย่างแพร่หลายในปัจจุบัน คือการถอดรหัสโดยอาศัยค่าซอฟต์หรือเรียกสั้นๆ ว่า “การถอดรหัสแอลดีพีแบบซอฟต์” โดยความหมายของค่าซอฟต์ในที่นี้คือ ค่าที่ใช้ในการบ่งบอกว่าแต่ละบิตที่ได้รับมาจากช่องสัญญาณ ควรจะเป็นบิต 0 หรือ 1 ด้วยความน่าจะเป็นเท่าไร การถอดรหัสแบบซอฟต์จะอาศัยค่าซอฟต์ของข้อมูลแต่ละบิต ส่งผ่านเส้นเชื่อมระหว่างโนดบิต และโนดเช็ค ตามเส้นทางที่แสดงบนกราฟแทนเนอร์ เพื่อทำการตรวจสอบว่า แต่ละบิตนั้น มีค่าความน่าจะเป็นในท้ายที่สุดเป็นอย่างไร โดยวิธีการส่งผ่านข้อมูลซอฟต์ผ่านทางโนดบิต และโนดเช็คจะสามารถเรียกอีกชื่อหนึ่งได้ว่า “การแพร่กระจายค่าความเชื่อมั่น (Belief propagation: BP)”  อัลกอริทึม BP เป็นอัลกอริทึมพื้นฐานในการส่งผ่านค่าซอฟต์ระหว่างโนดบิต และโนดเช็ค โดยมีเส้นทางเป็นไปตามเส้นทางของกราฟแทนเนอร์หรือตำแหน่งเลข 1 บนเมทริกซ์พาริตี้เช็ค \(\displaystyle \mathbf{H}\)  พิจารณาจากกราฟแทนเนอร์ที่แสดงในรูปที่ 4 จะพบว่า โนดบิตแต่ละโนดที่เชื่อมต่อกันภายใต้โนดเช็คที่ 1 มีความสัมพันธ์กันคือ  \(\displaystyle {{v}_{1}}+{{v}_{4}}+{{v}_{5}}+{{v}_{7}}=0\)  ฉะนั้น ข้อมูลแบบซอฟต์ที่ถูกส่งผ่านจากโนดเช็คที่ 1 มายังโนดบิตที่ 7 สามารถพิจารณาได้จากข้อมูลแบบซอฟต์ จากโนดบิตที่ 1, 4 และ 5 สามารถคำนวณได้จาก

\(\displaystyle \begin{array}{l}{{r}_{{17}}}(1)=P({{v}_{7}}=1,{{C}_{1}}|{{y}_{i}})\\\text{ = }P({{v}_{7}}=1,{{v}_{1}}+{{v}_{4}}+{{v}_{5}}+{{v}_{7}}=0|{{y}_{i}})\\\text{ = }P({{v}_{1}}+{{v}_{4}}+{{v}_{5}}=1|{{y}_{i}})\\\text{ = }\left[ {p({{v}_{1}}=1)p({{v}_{4}}=0)p({{v}_{5}}=0)} \right]+\left[ {p({{v}_{1}}=0)p({{v}_{4}}=1)p({{v}_{5}}=0)} \right]+..\\\text{ }\left[ {p({{v}_{1}}=0)p({{v}_{4}}=0)p({{v}_{5}}=1)} \right]+\left[ {p({{v}_{1}}=1)p({{v}_{4}}=1)p({{v}_{5}}=1)} \right]\end{array}\)

โดย \(\displaystyle {{C}_{1}}\) แสดงความสัมพันธ์ของแต่ละโนดบิตภายใต้โนดเช็คที่ 1 จากสัญญาณที่ได้รับ \(\displaystyle {{y}_{i}}\) และ \(\displaystyle P({{v}_{4}}=0)\) หมายถึง ค่าความน่าจะเป็นจากโนดบิตที่ 4 ที่ถูกส่งขึ้นไปบอกโนดเช็คที่ 1 ซึ่งสามารถเขียนให้อยู่ในรูป \(\displaystyle {{q}_{{41}}}(0)\) ย่อมหมายถึง การที่โนดบิตที่ 4 ส่งข้อมูลซอฟต์มาบอกโนดเช็คที่ 1 ว่ามีค่าความน่าจะเป็นที่จะเป็นบิต 1 เท่ากับเท่าไร อย่างไรก็ตามเราสามารถ เขียนให้อยู่ในรูปสมการแบบกระทัดรัด เพื่อที่จะสามารถนำมาใช้คำนวณค่าซอฟต์ที่ถูกส่งผ่านจากโนดเช็คมายังโนดบิตแต่ละโนด จะสามารถเขียนได้ดังสมการ

\(\displaystyle {{r}_{{ji}}}(0)=\frac{1}{2}-\frac{1}{2}\prod\limits_{{{i}’\in {{C}_{j}}\backslash i}}{{\left( {1-2{{q}_{{{i}’j}}}(1)} \right)}}\)

\(\displaystyle {{r}_{{ji}}}(1)=1-{{r}_{{ji}}}(0)\)

โดยที่ \(\displaystyle {{C}_{j}}\backslash i\) หมายความว่าทำการพิจารณาเส้นเชื่อมจากโนดบิตที่  \(\displaystyle {i}’\) ทุกๆ โนด ที่เชื่อมต่อกับโนดเช็คที่ \(\displaystyle j\) โดยที่ไม่รวมเส้นเชื่อมจากโนดบิตที่ \(\displaystyle i\) ในทางกลับกันสำหรับการส่งข้อมูลซอฟต์หรือค่าความน่าจะเป็นจากโนดบิตที่ \(\displaystyle i\) ไปบอกโนดเช็คที่เชื่อมต่ออยู่ในแต่ละเส้นทางนั้น สามารถคำนวณได้จากค่า \(\displaystyle {{r}_{{ji}}}\) จากแต่ละโนดเช็คที่เชื่อมต่อกับโนดบิตที่ \(\displaystyle i\) ซึ่งสามารถเขียนเป็นสมการในการคำนวณได้ดังนี้

\(\displaystyle {{q}_{{ij}}}(0)={{K}_{{ij}}}(1-{{P}_{i}})\prod\limits_{{{j}’\in {{V}_{i}}\backslash j}}{{{{r}_{{{j}’i}}}(0)}}\)

\(\displaystyle {{q}_{{ij}}}(1)={{K}_{{ij}}}{{P}_{i}}\prod\limits_{{{j}’\in {{V}_{i}}\backslash j}}{{{{r}_{{{j}’i}}}(1)}}\)

โดยที่ \(\displaystyle {{V}_{i}}\backslash j\) หมายความว่าทำการพิจารณาเส้นเชื่อมจากโนดเช็คที่ \(\displaystyle {j}’\) ทุกๆ โนด ที่เชื่อมต่อกับโนตบิตที่ \(\displaystyle i\) โดยที่ไม่รวมเส้นเชื่อมจากโนดเช็คที่ \(\displaystyle j\) ซึ่ง \(\displaystyle {{K}_{{i,j}}}\) คือค่าคงที่ที่ทำให้  \(\displaystyle {{q}_{{ij}}}(0)+{{q}_{{ij}}}(1)=1\) และ  \(\displaystyle {{P}_{i}}\) คือความน่าจะเป็นของโนดบิตที่ \(\displaystyle i\) มีค่าเท่ากับ 1 ซึ่งได้รับมาจากช่องสัญญาณสื่อสาร ฉะนั้น \(\displaystyle 1-{{P}_{i}}\) ย่อมหมายถึงความน่าจะเป็นของโนดบิตที่ \(\displaystyle i\) มีค่าเท่ากับ 0 อย่างไรก็ตาม ในกรณีของช่องสัญญาณเกาส์สีขาว ค่า  \(\displaystyle {{P}_{i}}\) สามารถหาได้จาก

\(\displaystyle {{P}_{i}}=\frac{1}{{1+{{e}^{{\frac{{-2{{y}_{i}}}}{{{{\sigma }^{2}}}}}}}}}\)

ผู้เขียนสามารถสรุปวิธีการถอดรหัสแอลดีพีซีด้วยอัลกอริทึม BP ได้ดังนี้

ขั้นเตรียมการ : กำหนดให้ตัวแปร \(\displaystyle X\) มีค่าเท่ากับ 0 จากนั้น ทำการกำหนดการวนซ้ำสูงสุดที่ต้องการให้มีค่าเท่ากับ \(\displaystyle k\)

ขั้นตอนที่ 1 : คำนวณค่า \(\displaystyle {{q}_{{ij}}}(0)\) และ  \(\displaystyle {{q}_{{ij}}}(1)\) ของทุกเส้นทางที่พุ่งออกมาจากแต่ละโนดบิต หาก \(\displaystyle k\)  ค่าเท่ากับ 1 จะกำหนดให้  \(\displaystyle {{q}_{{ij}}}(0)\) และ \(\displaystyle {{q}_{{ij}}}(1)\) มีค่าเท่ากับ \(\displaystyle 1-{{P}_{i}}\) และ \(\displaystyle {{P}_{i}}\) ตามลำดับ

ขั้นตอนที่ 2 : คำนวณค่า \(\displaystyle {{r}_{{ji}}}(0)\) และ  \(\displaystyle {{r}_{{ji}}}(1)\) ของทุกเส้นทางที่พุ่งเข้าแต่ละโนดบิต

ขั้นตอนที่ 3 :  คำนวณ \(\displaystyle X=X+1\) จากนั้นทำการวนซ้ำ ขั้นตอนที่ 1 – 3 จนกว่า  \(\displaystyle X\) จะมีค่าเท่ากับ \(\displaystyle k\) 

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

\(\displaystyle {{Q}_{i}}(0)={{K}_{i}}(1-{{P}_{i}})\prod\limits_{{j\in {{V}_{i}}}}{{{{r}_{{ji}}}(0)}}\)

\(\displaystyle {{Q}_{i}}(1)={{K}_{i}}{{P}_{i}}\prod\limits_{{j\in {{V}_{i}}}}{{{{r}_{{ji}}}(1)}}\)

โดย \(\displaystyle {{K}_{i}}\) คือค่าที่ทำให้  \(\displaystyle {{Q}_{i}}(0)+{{Q}_{i}}(1)=1\)

ขั้นตอนที่ 5 ทำการตัดสินใจด้วยความสัมพันธ์         

\(\displaystyle {{c}_{i}}=\left\{ {\begin{array}{*{20}{c}} {1,\text{ }{{Q}_{i}}(1)\ge {{Q}_{i}}(0)} \\ {0,\text{ }{{Q}_{i}}(0)>{{Q}_{i}}(1)} \end{array}} \right.\)

หมายเหตุ โดยปกติแล้ว เมื่อจำนวนรอบการวนซ้ำ \(\displaystyle k\) ค่าประมาณ 10~20 สมรรถนะในการถอดรหัสแอลดีพีซีจะมีการลู่เข้า

ใส่ความเห็น

อีเมลของคุณจะไม่แสดงให้คนอื่นเห็น ช่องข้อมูลจำเป็นถูกทำเครื่องหมาย *