รหัสแฮมมิ่ง

หลักการทั่วไปในการแก้ไขความผิดพลาด เมื่อต้องการเข้ารหัสข้อมูลจำนวน \(\displaystyle k\) บิต ให้เป็นคำรหัสที่ยาว \(\displaystyle n\) หากเราต้องการแก้ไขความผิดพลาดให้ได้ 1 บิต เราจะต้องมีค่าซินโดรม (syndrome) หรือตัวบ่งชี้อาการความผิดพลาดที่ต่างกันอย่างน้อย \(\displaystyle n+1\) ค่า กล่าวคือเราจะใช้ซินโดรมจำนวน \(\displaystyle n\) ค่า ในการระบุถึงตำแหน่งบิตที่ผิด และใช้ซินโดรมค่าสุดท้ายเพื่อบ่งบอกว่าไม่มีบิตผิดพลาดเกิดขึ้นเลย ฉะนั้นจำนวนบิตพาริตีเช็กที่ต้องใช้ \(\displaystyle m=n-k\) บิต จะต้องมากพอที่จะทำให้เงื่อนไข  \(\displaystyle {{2}^{m}}>n+1\) เป็นจริง ในกรณีของรหัสแฮมมิงนั้นมีคุณสมบัติพิเศษตรงที่สามารถใช้ประโยชน์จากบิตพาริตีเช็กในการแก้ไขความผิดพลาดได้อย่างเต็มประสิทธิภาพ กล่าวคือเงื่อนไขข้างต้นเป็นจริงสำหรับเครื่องหมายเท่ากับ “=”  ฉะนั้น สำหรับค่า \(\displaystyle m\) ค่าหนึ่งที่เลือกใช้จะได้ค่า \(\displaystyle n\) และ \(\displaystyle k\) ของรหัสแฮมมิงเป็นดังความสัมพันธ์ต่อไปนี้ 

\(\displaystyle \begin{array}{l}n={{2}^{m}}-1\\k=n-m={{2}^{m}}-m-1\end{array}\)

ตัวอย่างของรหัสแฮมมิง \(\displaystyle (n,k)\) ที่เป็นไปตามเงื่อนไขข้างต้นคือ \(\displaystyle (3,1),(7,4),(15,11),(31,26)\) และ \(\displaystyle (63,57)\) เป็นต้น

หลักการของรหัสแฮมมิ่งเป็นดังนี้คือ ข้อมูลที่จะทำการเข้ารหัสจะถูกแบ่งออกเป็นบล็อกข้อมูลขนาดเท่ากันจำนวน \(\displaystyle k\) บิต ซึ่งเขียนแทนด้วย 

\(\displaystyle \mathbf{m}=({{m}_{0}},{{m}_{1}},…,{{m}_{{k-1}}})\) 

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

\(\displaystyle \mathbf{b}=({{b}_{0}},{{b}_{1}},…,{{b}_{{n-k-1}}})\) 

และเมื่อนำบิตข้อมูลและบิตพาริตี้มาประกอบกันจะได้เป็นคำรหัส 

\(\displaystyle \mathbf{c}=({{c}_{0}},{{c}_{1}},…,{{c}_{{n-1}}})\) 

ซึ่งถ้าแสดงในรูปของสมการความสัมพันธ์จะได้ผลดังนี้คือ 

\(\displaystyle {{c}_{i}}=\left\{ {\begin{array}{*{20}{c}} {b,\text{  }i=0,1,…..,n-k-1} \\ {{{m}_{{i+k-n,}}}\text{      }i=n-k,n-k+1,…,n-1} \end{array}} \right.\)

นั่นคือ

\(\displaystyle ({{c}_{0}},{{c}_{1}},…,{{c}_{{n-k-1}}},{{c}_{{n-k}}},…,{{c}_{{n-1}}})=({{b}_{0}},{{b}_{1}},…,{{b}_{{n-k-1}}},{{m}_{0}},{{m}_{1}},…,{{m}_{{k-1}}})\)

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

\(\displaystyle {{b}_{j}}={{p}_{{0j}}}{{m}_{0}}+{{p}_{{1j}}}{{m}_{1}}+{{p}_{{2j}}}{{m}_{2}}+…+{{p}_{{k-1,j}}}{{m}_{{k-1}}}\) สำหรับ \(\displaystyle j=0,1,2,….,n-k-1\)

โดยสัมประสิทธิ์ \(\displaystyle {{p}_{{ij}}}\) จะมีค่าได้ 2 แบบเท่านั้น คือ 0 หรือ 1 ทั้งนี้ ค่าของ \(\displaystyle {{p}_{{ij}}}\) จะถูกกำหนดให้สอดคล้องกับความต้องการที่จะให้บิตพาริตี้ \(\displaystyle {{b}_{j}}\) มีความเกี่ยวพันกับบิตข้อมูลที่ \(\displaystyle {{m}_{i}}\) หรือไม่ นั่นคือ ถ้าไม่ต้องการให้มีความสัมพันธ์หรือขึ้นแก่กันก็กำหนด \(\displaystyle {{p}_{{ij}}}=0\) เพราะฉะนั้นจุดสำคัญของการเข้ารหัสจึงอยู่ที่การกำหนด \(\displaystyle {{p}_{{ij}}}\) ที่เหมาะสมเพื่อให้ได้คุณสมบัติตามที่ต้องการ

โดยทั่วไปในการศึกษารายละเอียดโครงสร้างของวิธีการเข้าและถอดรหัสบล็อกเชิงเส้นมักจะแสดงค่าต่าง ๆ ที่กล่าวมาข้างต้นในรูปของเมทริกซ์เพื่อให้เกิดความกระชับต่อการพิจารณา ในกรณีของรหัสแฮมมิ่ง \(\displaystyle (7,4)\) ก็เช่นเดียวกัน โดยสามารถบรรยายในรูปของเวกเตอร์ได้ดังนี้ 

                                                                             \(\displaystyle \mathbf{m}=[{{m}_{0}},{{m}_{1}},{{m}_{2}},{{m}_{3}}]\) 

                                                                             \(\displaystyle \mathbf{b}=[{{b}_{0}},{{b}_{1}},{{b}_{2}}]\)

                                                                             \(\displaystyle \mathbf{c}=[{{c}_{0}},{{c}_{1}},{{c}_{2}},{{c}_{3}},{{c}_{4}},{{c}_{5}},{{c}_{6}}]\)

                                                                             \(\displaystyle \mathbf{b=mP}\)

โดย

\(\displaystyle \mathbf{P}=\left[ {\begin{array}{*{20}{c}} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}} \right]\)

สำหรับเมทริกซ์ \(\displaystyle \mathbf{c}\) สามารถแสดงในรูปของ \(\displaystyle \mathbf{b}\) และ \(\displaystyle \mathbf{m}\)  ได้ดังต่อไปนี้

\(\displaystyle \mathbf{c}=[\mathbf{b}\text{ }\mathbf{m}]\)

นอกจากนี้ จากสมการข้างต้นเราจะได้ว่า

\(\displaystyle \begin{array}{l}\mathbf{c}=[\mathbf{mP}\text{ }\mathbf{m}]\\\text{ = }\mathbf{m}[\mathbf{P}\text{ }{{I}_{4}}]\end{array}\)

โดย \(\displaystyle {{I}_{4}}\) คือ เมทริกซ์เอกลักษณ์ขนาด 4×4 

\(\displaystyle {{I}_{k}}=\left[ {\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}} \right]\)

ถ้ากำหนดให้

\(\displaystyle \mathbf{G}=[\mathbf{P}\text{ }{{I}_{4}}]=\left[ {\begin{array}{*{20}{c}} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}\left| {\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}} \right.} \right]\)

ซึ่งเป็นเมทริกซ์ ขนาด 4 x 7 จากนั้นสามารถเขียนให้กระชับขึ้นได้เป็น

\(\displaystyle \mathbf{c=mG}\)

จากสมการจะเห็นว่า คำรหัส \(\displaystyle \mathbf{c}\) สามารถคำนวณได้จากการคูณชุดข้อมูล \(\displaystyle \mathbf{m}\) โดยตรงกับเมทริกซ์ \(\displaystyle \mathbf{G}\) ดังนั้น จึงเรียกเมทริกซ์ \(\displaystyle \mathbf{G}\) ว่า เมทริกซ์ตัวกำเนิด (generator matrix)

ที่กล่าวมาในข้างต้นนั้นเป็นการบรรยายความสัมพันธ์สำหรับใช้ในกระบวนการเข้ารหัส สำหรับส่วนต่อไปนี้จะอธิบายถึงการสร้างความสัมพันธ์ที่เป็นประโยชน์กับกระบวนการถอดรหัสนิยามเมทริกซ์ \(\displaystyle \mathbf{H}\) ที่มีขนาด  \(\displaystyle (n-k)\times n=(7-4)\times 7=3\times 7\) ขึ้นดังนี้

\(\displaystyle \mathbf{H}=[{{I}_{3}}\text{ }{{\mathbf{P}}^{\text{T}}}]=\left[ {\begin{array}{*{20}{c}} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\left| {\begin{array}{*{20}{c}} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{array}} \right.} \right]\)

โดย \(\displaystyle {{I}_{3}}\) คือ เมทริกซ์เอกลักษณ์ขนาด \(\displaystyle (n-k)\times (n-k)=3\times 3\) และ \(\displaystyle {{\mathbf{P}}^{\text{T}}}\) คือ เมทริกซ์ทรานส์โพสของ \(\displaystyle \mathbf{P}\) ซึ่งมีขนาดเท่ากับ \(\displaystyle (n-k)\times n=3\times 7\) ถ้านำเมทริกซ์ทรานส์โพสของ \(\displaystyle \mathbf{G}\) มาคูณทั้งสองด้านจะได้

\(\displaystyle \mathbf{H}{{\mathbf{G}}^{\text{T}}}=[{{I}_{3}}\text{ }{{\mathbf{P}}^{\text{T}}}]\left[ {\frac{{{{\mathbf{P}}^{\text{T}}}}}{{{{I}_{4}}}}} \right]={{\mathbf{P}}^{\text{T}}}+{{\mathbf{P}}^{\text{T}}}\)

จากคุณสมบัติของการบวกกันแบบมอดูโล 2 จะได้ว่า \(\displaystyle {{\mathbf{P}}^{\text{T}}}+{{\mathbf{P}}^{\text{T}}}=0\) โดยเมทริกซ์ที่คำนวณได้มีขนาด
เท่ากับ \(\displaystyle (n-k)\times k=3\times 4\) และมีสมาชิกเป็นศูนย์ทั้งหมด นั่นคือ 

\(\displaystyle \mathbf{H}{{\mathbf{G}}^{\text{T}}}=0\)

หรือหากพิจารณาในอีกลักษณะหนึ่งจะได้ว่า \(\displaystyle \mathbf{G}{{\mathbf{H}}^{\text{T}}}=0\) ด้วยเช่นกัน ซึ่งสามารถใช้ประโยชน์จากความสัมพันธ์นี้ได้โดยนำทรานส์โพสของเมทริกซ์ \(\displaystyle \mathbf{H}\) จากนั้นเราจะได้ 

\(\displaystyle \mathbf{c}{{\mathbf{H}}^{\text{T}}}=\mathbf{mG}{{\mathbf{H}}^{\text{T}}}=0\)

สมการนี้มีประโยชน์กับกระบวนการถอดรหัส ซึ่งจะอธิบายถึงวิธีการนำไปใช้งานในส่วนต่อไป สำหรับ
เมทริกซ์ \(\displaystyle \mathbf{H}\) มีชื่อเรียกเฉพาะว่า เมทริกซ์พาริตีเช็ก (parity-check matrix)     

พิจารณาการถอดรหัสแฮมมิง (7,4) ที่ภาครับ กำหนดให้ชุดบิตที่ได้รับเขียนในรูปของ
เวกเตอร์ได้เป็น 

\(\displaystyle \mathbf{r}=[{{r}_{0}},{{r}_{1}},{{r}_{2}},{{r}_{3}},{{r}_{4}},{{r}_{5}},{{r}_{6}}]\)

และกำหนดให้ความผิดพลาดของช่องสัญญาณสามารถเขียนได้ในรูปของเวกเตอร์

\(\displaystyle \mathbf{e}=[{{e}_{0}},{{e}_{1}},{{e}_{2}},{{e}_{3}},{{e}_{4}},{{e}_{5}},{{e}_{6}}]\)

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

\(\displaystyle \mathbf{r=c+e}\)

การถอดรหัสไปทำโดยการคำนวณหาค่าซินโดรมดังนี้ 

\(\displaystyle \mathbf{s=r}{{\mathbf{H}}^{\text{T}}}\mathbf{=(c+e)}{{\mathbf{H}}^{\text{T}}}\)

โดยที่อักนัยหนึ่งคือ \(\displaystyle \mathbf{s}=\mathbf{c}{{\mathbf{H}}^{\text{T}}}+\mathbf{e}{{\mathbf{H}}^{\text{T}}}\) มากกว่านั้นจากความสัมพันธ์จากสมการข้างต้นเราจะได้ \(\displaystyle \mathbf{s}=\mathbf{e}{{\mathbf{H}}^{\text{T}}}\) ความสัมพันธ์นี้แสดงให้เห็นว่า ค่าซินโดรมที่คำนวณได้ขึ้นกับค่าของความผิดพลาดของช่องสัญญาณเท่านั้น ไม่ขึ้นกับคำรหัสแต่อย่างใด ดังนั้น ค่าซินโดรมจึงสามารถนำมาใช้ระบุความผิดพลาดได้เนื่องจากเวกเตอร์ \(\displaystyle \mathbf{r}\) มีขนาด \(\displaystyle 1\times n=7\)  และเมทริกซ์ \(\displaystyle {{\mathbf{H}}^{\text{T}}}\) มีขนาดเป็น \(\displaystyle n\times (n-k)=7\times 3\) ดังนั้น เวกเตอร์ซินโดรม \(\displaystyle \mathbf{s}\) ที่ได้มีขนาด \(\displaystyle 1\times (n-k)=1\times 3\) โดยสามารถเขียนรายละเอียดการคำนวณหาค่าซินโดรมได้ดังนี

\(\displaystyle \begin{array}{l}{{s}_{0}}={{r}_{0}}\oplus {{r}_{3}}\oplus {{r}_{4}}\oplus {{r}_{6}}\\{{s}_{1}}={{r}_{1}}\oplus {{r}_{3}}\oplus {{r}_{5}}\oplus {{r}_{6}}\\{{s}_{2}}={{r}_{2}}\oplus {{r}_{4}}\oplus {{r}_{5}}\oplus {{r}_{6}}\end{array}\)

สังเกตว่าการหาค่าซินโดรมก็คือการตรวจสอบพาริตีเช็กแต่ละบิตว่าสอดคล้องกับที่คำนวณไว้ที่ภาคส่งหรือไม่นั่นเอง เมื่อได้ค่าซินโดรมครบทั้ง 3 บิต แล้ว ภาครับก็จะสามารถตัดสินใจได้ว่ามีความผิดพลาดเกิดขึ้นหรือไม่ และระบุตำแหน่งของบิตที่ผิดได้โดยอาศัยตารางในรูปที่ 3 จะเห็นว่าถ้าซินโดรมมีค่าเป็น 000 แสดงว่าไม่มีความผิดพลาดเกิดขึ้น แต่ถ้าซินโดรมมีค่าต่างไปจากนี้ตำแหน่งของบิตที่มีความผิดพลาดเกิดขึ้น ตัวอย่างเช่น หากมีความ ผิดพลาดเกิดขึ้นกับบิตแรกสุด นั่นคือ \(\displaystyle {{r}_{0}}\ne {{b}_{0}}\) ค่าซินโดรมที่ได้มีค่าเท่ากับ [1,0,0] หรือหากมีความผิดพลาดกับบิตสุดท้าย นั่นคือ \(\displaystyle {{r}_{6}}\ne {{b}_{3}}\) ค่าซินโดรมที่คำนวณได้คือ [1,1,1] จะเห็นว่าหากเกิดความผิดพลาดที่ตำแหน่งแตกต่างกันค่าซินโดรมที่คำนวณได้ก็แตกต่างกันด้วย ดังนั้น จึงสามารถใช้ค่า ซินโดรมเป็นตัวระบุตำแหน่งที่เกิดความผิดพลาดได้ รายละเอียดเป็นไปตารางในรูปที่ 3 เมื่อภาครับทราบตำแหน่งของบิตที่ผิดได้แล้วก็จะสามารถแก้ไขให้ถูกต้องได้เอง ทั้งนี้ หากมีความผิดพลาดเกิดขึ้นมากกว่า 1 บิต การถอดรหัสก็อาจจะไม่ถูกต้องอีกต่อไป ด้วยเหตุนี้ การพัฒนารหัสช่องสัญญาณที่มีขีดความสามารถในการแก้ไขความผิดพลาดได้หลายบิตมากกว่ารหัสแฮมมิงจึงเป็นเรื่องน่าสนใจ