錯誤更正碼簡介
https://www.math.sinica.edu.tw/media/pdf/d184/18404.pdf
－－－－－－－－－－－－－－－－－－－－－－－－－－－

數位世界的糾察隊－糾錯編碼的基礎及應用

張耀祖

糾錯編碼能控管數位通信、資料的品質，其理論與組合數學有著密切關係。本文介紹編碼的概念、發展史和應用，並透過實例來了解編碼的操作。

　　能夠交流複雜的資訊是人類建立文明的重要因素之一。隨著人類活動範圍的增大，通信變得越來越重要，如何正確無誤地傳遞訊息自然是極為重要的課題。而在步入數位時代的今天，要保證數位通信、數位影音、資料儲存的品質，靠的就是糾錯編碼！
　　先來看一個簡單的例子：假如在遊覽車上玩一個遊戲，主持人低聲唸幾個數字給坐第一排的同學聽，由他轉告第二排的同學，再由第二排的同學轉告第三排，一直傳到最後一排，再由最後一排的同學報出結果，只要數字一多，就容易出錯。這個例子說明了資訊的傳遞可能會出錯。
　　有些錯誤影響並不大，可有些情況卻不允許出錯，例如在外太空執行任務之無人飛行器的遙控訊號，就不允許有任何錯誤。在錯誤無法避免的情況下，如何正確地傳達指令？這就靠編碼來保證了！
　　現在再來看一個編碼的例子：某一年的北區大學博覽會，有資訊相關公司參展，並在會場贈送精美紀念品。有一位同學為了換紀念品，填寫了好幾份問卷，由於問卷上必須填寫身分證號碼，這位同學寫了自己的號碼，以及只換了最後一個數字的連號，他相信那些號碼都是正確而有效的號碼。
　　了解身分證號碼的編碼規則就知道，不可能有連號的情形。身分證號碼的最後一個數字是「檢查碼」(check digit)，是經由前面的英文字母和數字透過公式所產生的。只要檢驗該公式，就可以知道輸入的身分證號碼是否有效。因此，沒有檢查碼的英文字和數字就足以代表個人，檢查碼則是為了偵測整組號碼是否有效，才加上去的。這種加上檢查碼的作法就是「編碼」(coding)。身分證號碼的編碼只能偵測出是否有錯，這樣的編碼稱為「偵錯編碼」(error-detecting coding)。
　　有了偵錯編碼以後，如果收到一組錯誤的資料，而且錯誤數字的數量在某個範圍之內，就可以從收到的資料檢驗出來，只是無法得知錯在哪裡；如果有必要，可要求重新輸入或重新發送。身分證和國際標準書號(international standard book number, ISBN)都屬於這一類。如果想進一步知道錯在哪裡，就須使用「糾錯編碼」(error-correcting coding)。

糾錯編碼的發展史
第一個糾錯碼－漢明碼
　　糾錯編碼的想法始於1950年代，最早提出糾錯編碼的觀念，並建構出第一個糾錯碼的，是美國貝爾實驗室的漢明(Richard Wesley Hamming，圖一A)。
　　在1947年，電腦還是稀有之物，是只有特大型機關才用得起的貴重儀器。當時的電腦是一部多人使用的大型主機，大家透過終端機的鍵盤輸入工作指令，主機執行完再將結果傳回終端機。既然是大家一起用，就有所謂的優先順序，而漢明的使用層級不高，只能斷斷續續地利用各個週末，從家中連線到主機排隊等候。資料傳輸過程難免有錯誤產生，雖然當時也對傳送的資料做編碼保護，但用的是偵錯編碼，只能知道收到的資料是否有錯，一旦發現有錯就不執行而跳過，直接執行下一筆。
　　有一次漢明發覺，等候了幾個星期的工作沒有被執行，十分生氣。擁有數學背景的他開始思考：既然知道資料在傳送過程出了錯，為什麼不將它修正過來？這一氣使他著手從事編碼的改進，因而發展出第一個具有糾錯能力的編碼方法，現稱為漢明碼(Hamming code)。漢明不但創造出第一個糾錯碼，也建構了糾錯編碼理論的基礎，堪稱為糾錯編碼的開山始祖。由於漢明的重要貢獻，國際電子電機工程師學會(Institute of Electrical and Electronics Engineers, IEEE)在1998年設立了漢明獎(Hamming Medal)，而且第一屆得獎人就是漢明本人！
　　漢明雖然在1947年就構造出漢明碼，卻因為申請專利，直到1950年才出版論文。在這之前，資訊理論的創始人薛農(Claude Elwood Shannon，圖一B)，於1948年發表了＜通信的數學原理＞，提出了一個著名的結果，說明每個受到雜訊干擾的通道(Channel)，一定有一個容量，在不超過這個容量的前提下，會有一種編碼方式能正確無誤地傳送資料；也就是說，在接收訊息後能糾正所有在傳遞過程中產生的錯誤，而復原發送方所送出的訊息。但薛農在論文中只證明了糾錯編碼的存在性，並沒有提到如何建構編碼。
　　另一位編碼學者葛雷(Marcel J.E. Golay)，在讀了薛農的論文後受到很大的啟發，於是開始研究糾錯編碼，並在1949年發表全世界第一篇關於糾錯編碼的論文。該篇論文只有半頁多一點，後來被著名學者伯利坎普(Elwyn Ralph Berlekamp，薛農的學生)稱作是「最有價值的一頁論文」。這篇論文當中提到了葛雷碼(Golay code)－－這種編碼法在理論和實際應用上都非常重要，他與組合設計(combinatorial designs)、有限單群(finite simple groups)有著密切的關係。

　
圖一：糾錯編碼的兩位重要推手。(A)漢明碼的創始人－－漢明；(B)資訊理論的創始人－－薛農。

編碼法百花齊放
　　薛農的<通信的數學原理>為眾路英雄揭開「獵碼行動」的序幕，漢明碼、葛雷碼只是個開端，之後，各式各樣的糾錯編碼便如雨後春筍般，一一冒出頭來。
　　1954年，穆勒(David E. Muller)提出里德-穆勒碼(Reed-Muller code，簡稱RM碼)，不久之後，里德(Irving Stoy Reed)針對該碼提出一個更好的代數構造法，同時也提出一個很好的解碼法。1971年5月30日發射的水手九號(Mariner 9)上，用的就是RM碼，整個任務共將7329張火星的黑白照片傳回地球。
　　1959年的時候，霍昆格姆(Alexis Hocquenghem)以法文發表了一篇論文，提出一類能糾正多個錯誤的碼；而在隔年，玻士(Raja Chandra Bose)和雷喬德赫瑞(Dwijendra Kumar Ray-Chaudhuri)，也以英文發表了一篇結果相似的論文。這個碼後來被稱為BCH碼，是個實用而且重要的碼，被運用在衛星通信和隨身碟等。坡士為組合設計方面的先驅人物之一，而雷喬德赫瑞是他的學生，他們從組合學的觀點來建構編碼，並不令人意外，畢竟組合觀點比代數結構直覺多了。
　　1960年，里德和索羅門(Gustave Solomon)發表了一篇只有五頁的文章，文中提出一類新的糾錯碼，稱為里德-索羅門碼(簡稱RS碼)。RS碼後來被廣泛應用在各個層面，從臥房中的雷射唱片播放機，一直到已離開太陽系的深空探測機(deep space craft)旅行者號。現在的CD、DVD和藍光DVD，甚至是WAP手機、藍芽技術，也都用到了RS碼。
　　1967年，伯利坎普發表了一個非常有效率的解碼演算法，兩年後梅西(James Lee Massey)提出一個等價的硬體版本，這個演算法讓RS碼成為實用上最重要的碼。到現在伯利坎普-梅西演算法仍然是一個非常重要的解碼演算法。
　　最後，還要介紹的是「平方剩餘碼」(quadratic residue code，簡稱QR碼)。平方剩餘碼是由普朗基(Eugene Prange)在1958年所提出的，其中包括了漢明碼和葛雷碼，伯利坎普稱它為「很難解碼的好碼」，且因為它的重要性，幾乎每一本編碼教科書都會提到這個碼。里德在1991年開始致力於解平方剩餘碼，與他的學生張肇健(T. K. Truong)等陸續解出了幾個碼。
　　1995年，張肇健接受義守大學校長的邀請，辭去美國航太總署與南加州大學的工作，來到台灣擔任義守大學電機資訊學院院長，並帶領義守編碼團隊繼續研究平方剩餘碼的解碼，後來成功地解出包括碼長113位以內的所有未解碼，讓義守大學的編碼團隊在國際間打出了名號。
　　由於篇幅的關係，其他重要的碼，如卷積碼(convolutional code)、渦輪碼(turbo code)、LDPC碼(low-density parity check code)等，並不在這裡做介紹。

糾錯編碼的應用
　　糾錯編碼有非常多應用，只要牽涉到數位的，幾乎都會用到糾錯編碼，例如衛星通信、隨身碟、硬碟、手機、無線電話等，這裡我們只舉兩個例子來說明，這兩個例子都用了RS碼。

雷射唱片
　　第一個例子是雷射唱片(compact disc, CD)，CD是第一個使用糾錯編碼的消費性電子產品。
　　不知道讀者家中有沒有傳統的唱片？那種直徑約20~30公分的唱片，不能亂放，亂放容易變形；播放時要小心翼翼，收拿之際也不可掉以輕心，怕一個不小心就刮傷了唱片。刮傷了唱片會怎麼樣？小則在播放時會出現「波」一聲的雜音，大則這一面就此報廢。只是聽個音樂而已，有必要那麼緊張兮兮嗎？即使一切都沒有問題，播放時也容易因靜電而出現「小音爆」。除了這些問題外，傳統唱片也不耐久播。有些人心愛的唱片24小時內絕不播放兩次；也有愛樂者看到鍾愛的唱片，會一口氣將相同的數張全部買下，為的是多作儲備可免斷糧之虞。這一切，是新一代愛樂者無法想像的。
　　上述的這些苦難，在CD唱片出現之後就不復再現。
　　小小一片直徑12公分的CD到底有多大能耐，能免除前面提到的困擾，不也同樣是在唱盤上播放嗎？為什麼不怕小刮痕(太大的刮痕當然也會有問題)？為什麼可以不限次數地連續播放？而用了幾年的CD和新買的播放起來沒有兩樣。這是怎麼做到的？答案就是數位化再加上糾錯編碼。
　　數位化讓CD能提供完全沒有雜音的完美音響，以及任君指定的播放順序。而使用糾錯編碼，能讓CD可以不怕指紋、不怕刮痕。CD所使用的糾錯編碼是RS碼，理論上，可以糾正一串軌道長度達2.5毫米的訊號。筆者以前清除CD的灰塵，都按照音響雜誌的指示，用清潔工具小心地清理；接觸糾錯編碼之後，就直接拿CD在衣服上清除灰塵。(請注意，並不鼓勵讀者這麼做！)
　　除了沒有上述傳統唱片的缺點之外，CD唱片還有許多優點，其中之一是播放時間長－－CD的連續播放時間最多長達74分鐘，相較之下，傳統黑膠唱片只能連續播放30分鐘，著實遜色不少。至於為什麼是74分鐘？原來，這是為了要能不換片而一口氣聽完貝多芬的《合唱交響曲》呢！

外太空的訊號傳遞
　　美國航太總署在1977年8月20日發射了旅行者二號(Voyager II)，並在同年的9月5日發射了旅行者一號。旅行者號的任務之一，是從較近的距離拍攝天體的照片，並傳送回地球。由於太空船一旦發射出去，便無法補充能源，而能源不僅要維持太空船的正常運作，又要用於拍照並將訊息傳回地球，因此不能用太多的能源來傳送信號。太空船傳訊所用的能量約為5瓦，這樣的能量只能夠點亮一個小燈泡；用這麼小的能量傳遞數十億公里的距離，收到有錯的資料是可以預期的，因此一定要用編碼保護。
　　旅行者號的影像處理方式為，將一張全彩照片轉化為3個800×800的矩陣，每個陣元為8位元的像素(pixel)，也就是說，一張照片需要3×800×800×8=15,360,000個位元(bits)的數位訊號。旅行者號早先在土星傳送的資料都未經壓縮，是以葛雷碼編碼後傳送回地球；地球上收到訊號，經過解碼便可重建原來的照片。1982年旅行者號到達天王星，距離由土星的14億公里倍增為28億，因此便採用由萊斯(Robert Rice)提出的2.5倍壓縮比的無損壓縮演算法，對資料進行壓縮，再做糾錯編碼後傳回地球。由於經過壓縮的資料更是錯不得，所以將糾錯編碼換成糾錯能力更強的RS碼，之後在海王星也是使用RS碼。
　　目前旅行者號已經離開太陽系，因此，離開太陽系的深空探測器增加為四個，分別是先鋒十號、十一號，以及旅行者一號、二號。目前，旅行者二號仍然盡可能地將資料傳回地球，讓科學家獲得具體的數據，以研究過去無法探知的區域。最後，即使燃料完全用完，它們也都帶著一張儲存地球上各種影音資料的鍍金唱片(先鋒號帶的是鍍金鋁板)，要讓那些可能存在的地外文明，也能了解地球文明。

糾錯編碼的實例
　　看了這麼多文字介紹，接下來，我們要從一些簡單的例子，實際了解糾錯編碼。
　　假設要傳送art這個字，先依照表一將英文字母數位化。於是英文單字art就被轉換為數字串「00001」、「10010」、「10100」。接著，將數字串送出。假設傳送的過程中，第2、12個位置出了錯，則送出和收到訊號分別為：
送出：00001 10010 10100
收到：01001 10010 11110

表一：英文字母數位編碼一覽表

字母	編碼	字母	編碼	字母	編碼
a	00001	j	01010	s	10011
b	00010	k	01011	t	10100
c	00011	l	01100	u	10101
d	00100	m	01101	v	10110
e	00101	n	01110	w	10111
f	00110	o	01111	x	11000
g	00111	p	10000	y	11001
h	01000	q	10001	z	11010
i	01001	r	10010

　　由收到的資料解讀，每五個數字一組，解讀後得出「ir?」，無法確定是什麼字，除了第三個字母確定是錯的之外，其他的無從判斷是對是錯，要猜也無從猜起。為了避免這種的情形，在資料傳送前，都會對資料預做編碼處理。請看下面兩個編碼的例子。

奇偶校驗碼
　　奇偶校驗碼(parity-check code)是將原來的數字串分成兩個兩個一組，不足兩個的，補上0使其成為一組。接著，對每一組數字加入一個檢查碼，成為三個一組的數字串。加檢查碼的方式如下：
00→000
01→011
10→101
11→110
則原始資料的編碼流程為：
原始資料：000011001010100
補成偶數：0000110010101000
編碼後：000000110000101101101000
假設，傳送的過程中同樣在第2、12個位置出了錯，因此收到了：
010000110001101101101000
按照原先的編碼方式，解碼的方式為：
000→00
011→01
101→10
110→11
　　由於收到的前三個數字為010，不在規則內，因此解碼結果為「??」，也就是說遇到不在規則內的就解碼為「??」。則解碼後的結果如下：
　　解碼後；?? 00 11 ?? 10 10 10 00
前五個數字為「??001」，當然無法變成英文字母，之後的五個數字「1??10」也一樣，接著的五個數字「10100」，對應到英文字母t，後面留下一個0，表示是補上去的，可以忽略。因此最後得到的結果為「??t」。
　　這種編碼方式可以看出有錯(只要不在事先約定的規則內，就是有錯)，但是無法知道錯在哪裡，也就是說，只具備偵錯功能，不具備糾錯功能。

三倍重複碼
　　三倍重複碼(triple repetition code)是將每組兩個數字編碼為六個數字，而且是採用重複三次的方式做編碼，如下：
00→000000
01→010101
10→101010
11→111111
直接從補上零的原始字串進行編碼，得到：
000000 000000 111111 000000 101010 101010 101010 000000
同樣地，假設傳送的過程中第2、12個位置出了錯，因此收到了：
010000 000001 111111 000000 101010 101010 101010 000000
三倍重複碼解碼的方式如下：
000000→00
010101→01
101010→10
111111→11
前六個數字為「010000」，並不在規則內，表示一定有錯。由於編碼的方式是將ab編為ababab，表示第一、三、五個數字要相同，不同表示有錯；第二、四、六個數字的情形也是一樣。收到的「010000」的第一、三、五個數字都是0，可以視為無錯，而第二、四、六個數字分別1、0、0，表示一定有錯。如果第二個是錯的，則三個數字就都是0，反之，如果第四、六個數字有錯，則三個數字都是1。兩個情形都有可能，那麼要選哪一種好呢？解碼的原則是選擇可能性最大的，稱為「最大可能性解碼」(maximum likelihood decoding)。
　　錯一個和錯兩個，哪一種可能性比較大？一般來說，資料傳送時，出錯的可能性不能太大，在美國航太總署的太空任務中，可接受的最大出錯機率為一千個錯一個，也就是說每個數字出錯的機率為千分之一，兩個數字同時出錯的機率就是千分之一的平方－一百萬之一。上面的兩種情況相比，當然錯一個機率比較大，因此，「010000」應該解為「00」。同樣地，第二組數字「000001」應解為「00」，而剩下的部分沒有錯，都能正確解出，因此最後解碼後的結果為「00001 10010 10100」，由這串數字可以正確解出英文字「art」。這就是一個糾錯編碼的實例。
　　上面的這個例子是一個最簡單的情況。目前整個編碼學已建立在嚴格的數學理論基礎上，要用到組合理論、機率、抽象代數、有限體(finite field)等；而要能理解實際的應用，還要加上演算法(algorithm)和硬體等實作方面的知識。有了這些知識，就能對糾錯理論有更深刻的體會。

結語
　　隨著科技的進步，以往的電話只能聽到聲音，現在的手機還能邊講話邊看到對方，又能傳送音樂、照片和影像；回到家裡打開電視，就能看到上百個來自於有線、無線電視台的高畫質數位節目。如果沒有糾錯編碼，這一切只能是科幻小說中的情節。隨著生活品質的提升，我們對編碼的需求也更加殷切，身為一個現代人，怎能對這個概念一無所知呢？希望這篇文章，能讓你對糾錯理論有個基本的認識。最後，關於組合學以及更多的數學知識，有一本非常好的中文雜誌－－《數學傳播》，現在該雜誌的所有文章都已經放在網路上，歡迎讀者下載閱讀。

參考資料
1. 有澤創司，陳文棠譯，《SONY才子－－大賀典雄傳奇》，台北，迪茂國際出版公司，2001年。
2. 大賀典雄，劉錦秀譯，《指揮家與總裁》，台北，商周出版，2006年。
3. 王勝治，《數位雷射音響》，全華科技出版社，1992年。
4. 萬哲先，《代數和編碼》，北京，科學出版社，1980年。
5. 馮克勤，《代數與通信》，北京，高等教育出版社，2005年。

－－－－－－－－－－－－－－－－－－－－－－－－－－－
http://gclie.users.sonic.net/gclie/ecc.pdf

錯誤訊息的偵測與修正

賴紹正

為什麼條碼機可以正確地讀出你購買的商品價錢？為什麼稍稍刮損的音樂CD仍可播放？數位訊息中暗藏著什麼祕密，且讓我們來一探究竟。

　　筆者在《科學月刊》第468期（2008年12月號）的〈GPS的定位數學〉裡提到，衛星發射信號的功率在50瓦左右，我們也談到衛星的飛行高度大約在2.5萬公里左右。因訊號的強度與距離的平方成反比，故其到達地球表面的訊號強度大約只有 瓦／平方公分，是非常弱的。相較之下，一般家用無線網路的功率大約在0.1瓦，其有效距離在100公尺內，其強度尚有 瓦／平方公分。因此GPS的接收機應比家用無線網路的接收機敏感多了！

　　即使如此，我們還是很難想像，它能完全無誤地接收訊息，更何況衛星發射器本身及傳遞的過程中均可能產生錯誤訊息。GPS是用來定位的，些許的錯誤訊息很可能造成「差之毫釐，失之千里」！例如某顆衛星在台北的上空，但一字之差，接收機以為它在台南上空，計算後可能告訴你，你即將掉進台灣海峽了！如何解決此類問題正是本文所要探討的。

類比vs.數位
　　要避免像上述掉進台灣海峽的烏龍事件發生，接收機的首要功能應是能偵測到訊息的錯誤。在現今所謂的資訊時代，具備此一功能的設備，事實上已是日常生活中不可或缺的工具，只是大部分的人都沒有注意到而已。例如百貨公司所用的條碼機就有此一功能，相信許多讀者都有這個經驗：第一次掃描若發生錯誤，條碼機就會告訴服務員要重新掃描一次。可是條碼機如何知道它讀的資料有誤呢？

　　很顯然地，錯誤訊息的偵測一定是存在訊息本身內的。在討論訊息本身如何「儲存」偵測錯誤的能力之前，我們得先在這裡談一下訊息結構的種類。訊息的結構與傳播可分為類比（analog）及數位（digital）兩種。早期的訊息幾乎全是類比，類比的訊息是以波動的連續變化來儲存與傳遞；但隨著微電腦及積體電路的不斷改進，數位訊息的使用已越來越廣泛。數位訊息是以數碼的形式來儲存與傳遞訊息，如果原訊息是類比訊息，則須先將它數位化（digitalize）。數位訊息的最大優勢是可輕易且正確地複製及處理，以及本文所要談到的：可以輕易地偵測到訊息本身的錯誤並修正它。

錯誤訊息的偵測
　　如果圖一中的波形受干擾，發生不怎麼大的變形，我們無法判斷到底是因為「原來的信號就是如此」或是「錯誤」所致。但如果是圖二中的信號「50300702」受到少許的干擾，如5 的高度變成5.2，則因為訊息只有整數的，故我們可以毫無困難地知道（偵測到）5.2是錯誤的，應該修正為5 才對。這正是一種錯誤訊息的偵測與修正，相信是大家均早已知曉的數碼傳遞優點；但因其邏輯簡單，沒什麼研究可做（申請不到任何研究經費的），因此一般都不把它歸入「錯誤訊息的偵測與修正」。
　　聰明的讀者也許立即想到：如果干擾較大點，變成5.6呢？不錯，那我們的接收器只好把它當成6了。沒問題，雖然產生了「這麼大」的錯誤，但我們還是有辦法知道接收的訊息錯了，例如我們「規定」每8個數目的總和必須是奇數(\(  5+0+3+0+0+7+0+2=17 \))，則第一個數目誤接收為6時，其總和變為偶數。錯了，請服務員再掃瞄一次吧！
　　如果干擾更大，5變成7怎麼辦呢？上面的奇數策略當然就不管用了。但要解決此一難題，事實上很簡單：我們可以「規定」8個數目的總和必須是9的倍數就可以了。當然，在條碼的運用上，這種「規定」很容易做得到。但如果應用到其他由類比數位化成的訊息時，就很難加以這樣「規定」(限制)了。解決此一問題的方法，事實上正是所有偵測訊息錯誤所採用的方法－－在訊息本身外加上其他「冗位」(redundancy)的資料。例如在前面所用的8位數資訊後，我們可以再加一位數，成為9位數的字碼(codeword)。這樣我們就不須要「限制」前面的8位數(它們可以是由任何數字組成的)，仍然可以達到字碼必須是9的倍數之要求(圖三)。請讀者在此特別注意：這冗位的數字不是隨便給的，而是由資訊本身(更正確地說，應是字碼本身)「計算」得來的－－字碼必須是9的倍數！

\( \underbrace{\overbrace{50300702}^{資訊}1}_{字碼} \)

圖三：在這串訊息中，前8位數為有用的資訊，最後一位則是「冗位」，總共是9位數的字碼。

　　利用此一「編碼法」，我們可以很容易地偵測出字碼錯誤(不是9的倍數)，但卻不知錯誤在那裡。這用在條碼等訊息傳輸上不是大問題－－只要使用者(例如服務員)再重讀一次即可[註一]。但在很多的實用方面卻會構成大問題；例如在聽音樂CD時，我們不能叫聽者暫停，讓CD播放機重讀一下錯誤的訊息[註二]。因此在許多實用上，我們不只要有偵測錯誤訊息的能力，還須具備即時修正的能力，底下我們就來談談錯誤訊息的修正。

錯誤訊息的修正
　　在前面的例子裡(字碼必須是9的倍數)，我們只要將字碼連續傳遞兩次，則我們不但能偵測到訊息的錯誤，還可以同時完成修正。例如我們收到的訊息是：\(  \underbrace{503007021}\underbrace{505007021} \)

但我們不但知道訊息有誤，還知道第三位數應是3而不是5(因第三位數不同，且總和應是9的倍數)，這結果看來非常好，但仔細一想，未免太浪費「資源」了：本來只要傳遞8位數的訊息，現在卻須傳遞18位數。這「資源」在訊息傳播上稱為頻寬(bandwidth)。頻寬就像土地一樣，隨著人口的增加及生活水準的不斷提升，正是寸土寸金浪費不得的。
　　相信不少讀者早就想問：如果有兩位數字同時發生錯誤怎麼辦？答案很簡單：沒辦法，此編碼法不能用於修正同時含兩個(或兩個以上)錯誤的訊息。那怎麼辦呢？其解決方法有二：其一是尋根究底改進訊息的產生與傳遞，以及接收的機構，來降低錯誤的發生率到編碼法可以輕鬆完成任務的地步；其二則是設計「更好」的編碼方法，本文後面將會談論到。
　　在這裡順便一提，所有錯誤訊息的偵測及修正法均是採用原訊息中增加「冗位」的資料來完成的。這看來在資訊的儲存上似乎是個浪費，但如果仔細分析，就會知道這結論並不完全正確。例如在錄音帶的系統中，因有偵測及修正錯誤的能力，我們可以減低對訊號雜訊比(signal to noise ratio)的要求，而使用較狹窄的錄音帶。
　　到此為止，筆者所談的錯誤偵測與修正法，均可用直覺來推斷，缺少理論的基礎，但筆者相信已將其原理用白話清楚地表達出來。實用的編碼方法很多，也都有數學基礎，但那數學卻不是一般高中或大學所涉及的[註三]，因此我們在此不擬討論其推理，而僅說明結果。底下就是個無法用「直覺」想出來的例子－－音樂CD編碼的基本原理，如果不是數學家早有研究，相信索尼(Sony)及飛利浦(Philips)不會那麼快就發展出今日的CD標準。

漢明碼
　　為了能夠清楚地說明漢明碼(Hamming codes)，我們將以一個由7個二進位數組成的字碼來做為例子： \( \underbrace{1010}_{資訊}\underbrace{001}_{檢測} \)
　　前面4位數是(有用的)資訊，而後面的3位數則是我們前面所談到之「冗位」資料，在錯誤訊息的偵測與修正上，一般稱為「同位位元」(parity bit)。用3位數來檢測與修正4位元的資訊，好像也比前面的10:8之頻寬浪費好不了多少。不錯，但這是為了說明方便，所以才採用3位元來檢視。如果我們採用4位元來檢測，則有用的資料長度可達11位元；用5位元來檢測與修正，有用的資料長度可高達26位元！
　　如前所述，同位位元並不是隨便加進去的，必須依一定規則計算出來。如果我們用\( b_1 \)、\( b_2 \)、\( b_3 \)及\( b_4 \)來代表前面的資訊，則後面3位檢測位元\( p_1 \)、\( p_2 \)及\( p_3 \)依數學分析將分別為：\( \matrix{p_1=b_1+b_2+b_3 \cr p_2=b_1+b_3+b_4 \cr p_3=b_2+b_3+b_4} \)
　　上面的「+」為二進位運算中的「互斥或(exclusive OR)」：\( \matrix{1+1=0 \cr 1+0=1 \cr 0+1=1 \cr 0+0=0} \)
　　所以如果資訊為1010，我們得：\( \matrix{p_1=1+0+1=0 \cr p_2=1+1+0=0 \cr p_3=0+1+0=1} \)。將這3位檢測位元加到原資訊後面，我們便得字碼：1010001。如果我們收到的字碼為\( (b_1b_2b_3b_4p_1p_2p_3) \)，我們如何偵測及修正錯誤呢？我們由所接收的字碼計算出3個「接收檢測位元」：\( \matrix{Q_1=b_1+b_2+b_3+p_1 \cr Q_2=b_1+b_3+b_4+p_2 \cr Q_3=b_2+b_3+b_4+p_3} \)

如果接收到之字碼沒錯，則\( Q_1=Q_2=Q_3=0 \)；如果僅有一位位元有錯(此一漢明碼不能同時偵測兩個或以上之錯誤)，則其中至少有一Q不為0，我們可由\( Q_1,Q_2,Q_3 \)之值推斷錯誤所在處如下[註四]：
\( (1,1,0)→b_1 \)
\( (1,0,1)→b_2 \)
\( (1,1,1)→b_3 \)
\( (0,1,1)→b_4 \)
\( (1,0,0)→p_1 \)
\( (0,1,0)→p_2 \)
\( (0,0,1)→p_3 \)
　　然後將錯誤處之值0→1或1→0即可。例如原字碼1010001，但我們收到為1110001，則我們得：\( \matrix{Q_1=1+1+1+0=1 \cr Q_2=1+1+0+0=0 \cr Q_3=1+1+0+1=1} \)
　　即\( (Q_1,Q_2,Q_3)=(1,0,1) \)，所以我們可以得知\( b_2 \)是錯誤的！這些計算看來雖然不怎麼複雜，不過似乎很繁瑣；但其運算方式是計算機設計的基本邏輯，因此可以利用微電腦線路，完全自動化地偵測及修正接收到的資訊。

里德-所羅門碼
　　在音樂CD中所用的錯誤偵測原理雖然與上面的例子相似，但當然要比它複雜多了。我們上面例子裡的每個二進位位元，在音樂CD裡則是由8位位元組合的「符號」(symbol)；檢測位元也是由符號組成的。它的字碼由24個資料符號及8個檢測符號組成(共32個符號)，可以同時偵測及修正4個資料符號。此一「編碼法」是里德(Irving Reed)及索羅門(Gustave Solomon)於1960年，在美國麻省理工學院林肯實驗室發展出來的，稱為里德-索羅門碼(Reed-Solomon codes，簡稱RS碼)。
　　為了能修正「大面積」錯誤(burst error)，此編碼法更將原來一連串符號(包括檢測符號)交錯記錄於音樂CD內，這樣原來RS碼無法修正的大面積錯誤(大於4個資料符號)在復原時就被「打散」成許多RS碼可以處理的小面積(等於或小於4個資料符號)錯誤。在音樂CD的編碼上，此一做法稱為「交叉插入里德-索羅門碼(cross interleave Reed-Solomon code，簡稱CIRC)」。這說明了為什麼在音樂CD上刮一道(請勿輕易嘗試)，有時還是不會失真的原因。當然，要產生原來音樂前，得先將交錯復原後再解碼。

結語
　　隨著微電腦及積體電路的不斷改進，數位訊息的使用已越來越廣泛：從微電腦本身到MP3、音樂CD、DVD影碟機、電影、錄影機、照相機、無線電廣播、電視、電台……等等。數位訊息最大的優勢是處理(如修改)容易、可輕易且完美地複製、以及「很容易地」偵測到其傳遞錯誤的訊息並修正之。本文不用數學，簡單地介紹了數位訊息傳遞錯誤的偵測與修正的基本原理：在原訊息中增加「多餘」的「同位位元」來達成(例如音樂CD裡就多加了三分之一同位位元)。雖然我們未能深入地討論其數學，但希望讀者還是能因本文而了解到，看似簡單的日常用品後面，事實上是暗藏了常被視為無用之「純」數學的研究成果。



註一：電腦的記憶體就是使用此一原理(9位元，其中有一位元是屬於「冗位」的)；但因電源及其設計越來越穩定，不少個人電腦都已開始採用不須「冗位」位元的記憶結構(買記憶體時應注意)。
註二：隨身聽音樂CD播放機因隨時在動的關係，其錯誤訊息出現的頻率遠超過家用音樂CD播放機，因此必須常常利用重讀來解決錯誤的問題，所以較貴的CD隨身聽機都有所謂的「抗震」功能。它們是先將資料儲存於緩衝區，然後依序播放。緩衝區越大，抗震的能力當然也越大。緩衝區使得它們有時間(不須暫停)去重讀錯誤的資料。
註三：所用的數學為抽象代數學(abstract algebra)中的場(field)論。我們所熟知的一個例子是：所有的實數及其運作(加減及乘除)規則構成了一個抽象代數中的「(無限)場」(因具有無限的實數)。
註四：如果讀者對排列組合有興趣，可以輕易算出 不全為0的情形共有7種，這正是7位元資訊單一錯誤的可能情形！利用此一分析，讀者也可了解為什麼我們在文中說：「如果採用4位元來檢測，則有用的資料長度可達11位元」了。

－－－－－－－－－－－－－－－－－－－－－－－－－－－
110.1.29補充
Hamming codes and error correction
https://www.youtube.com/watch?v=X8jsijhllIA
Hamming codes part 2, the elegance of it all
https://www.youtube.com/watch?v=b3NxrZOu_CE

11.秘密分享方案介紹－R. J. McEliece and D. V. Sarwate

這個方案是基於Reed-Solomon糾錯編碼，詳細內容請見
R. J. McEliece and D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Comm. ACM, Vol. 24 (1981), 583-584.
https://dl.acm.org/doi/pdf/10.1145/358746.358762

由Adi Shamir提出的著名「秘密分享機制」(Secret Sharing Scheme)，實際上可以被視為「里德-所羅門碼 (Reed-Solomon Codes)」編碼理論中的一個特例。若將秘密分享問題置於編碼理論的框架下進行探討，將帶來許多顯著的優勢。

最大的優勢在於能夠利用里德-所羅門碼強大的「錯誤與抹除解碼算法」(errors-and-erasures decoding algorithm)。這意味著，即使部分「秘密份額 (pieces of the secret)」因為惡意篡改(錯誤)或儲存媒介損壞(抹除)而變得不可信，只要收集到足夠數量的(包含錯誤的)份額，依然可以透過解碼算法找出哪些份額是錯誤的，並成功還原出原始的秘密。

1.Shmir秘密分享
設秘密為\(S\)，\(n\)個人共享秘密，至少要\(k\)位才能重組秘密 \(f(x)\)為\(k-1\)次多項式，其中常數項為秘密\(S\)，其餘各項係數為隨機整數 計算\(f(x)\)上\(n\)個點座標，將各個座標分派給\(n\)個人 Shamir's secret sharing的\(\displaystyle f(x)=\sum_{i=0}^{k-1}a_ix^i\)等同於 Reed-Solomon錯誤校正碼的\(\displaystyle p_m(a)=\sum_{i=0}^{k-1}m_i a^i\)	範例出自Shamir's secret sharing 設秘密為\(S=1234\)，\(n=6\)個人共享秘密，至少要\(k=3\)位才能重組秘密 \(f(x)\)為\(k-1=2\)次多項式，其中常數項為秘密\(S\)，1次項和2次項係數為隨機整數 \(f(x)=1234+166x+94x^2\pmod{1613}\) 計算\(f(x)\)上6個點座標 \(f(1)=1234+166\cdot 1+94\cdot 1^2=1494\equiv 1494\pmod{1613}\) \(f(2)=1234+166\cdot 2+94\cdot 2^2=1942\equiv 329\pmod{1613}\) \(f(3)=1234+166\cdot 3+94\cdot 3^2=2578\equiv 965\pmod{1613}\) \(f(4)=1234+166\cdot 4+94\cdot 4^2=3402\equiv 176\pmod{1613}\) \(f(5)=1234+166\cdot 5+94\cdot 5^2=4414\equiv 1188\pmod{1613}\) \(f(6)=1234+166\cdot 6+94\cdot 6^2=5614\equiv 775\pmod{1249}\) 將\((1,1494),(2,329),(3,965),(4,176),(5,1188),(6,775)\)分派給6個人
2.當\(k\)個人聚在一起要重建秘密(無錯誤情況)
有\(k\)個人聚在一起要重組秘密\(S\)，利用拉格朗日插值多項式計算出\(f(x)\) 秘密為\(S=f(0)\)	假設第2,4,5位聚在一起要重組秘密\(S\)，利用拉格朗日插值多項式根據\((2,329),(4,176),(5,1188)\)計算出\(f(x)\) \(\displaystyle f(x)=329\frac{(x-4)(x-5)}{(2-4)(2-5)}+176\frac{(x-2)(x-5)}{(4-2)(4-5)}+1188\frac{(x-2)(x-4)}{(5-2)(5-4)}\) 　　\(\displaystyle =329\frac{(x-4)(x-5)}{6}-88(x-2)(x-5)+396(x-2)(x-4)\) 　　\(\equiv 329\cdot 269(x-4)(x-5)-88(x-2)(x-5)+396(x-2)(x-4)\pmod{1613}\) 　　\(\equiv 1234+166x+94x^2 \pmod{1613}\) 秘密為\(f(0)=1234\)
3.有錯誤情況用Berlekamp-Welch演算法修正解碼
設\(e\)為發生錯誤數量，錯誤位置多項式\(\displaystyle E(x)=\sum_{i=0}^{e}e_i x^i\)，最高次方係數\(e_e=1\) (1)當\((a_i,b_i)\)為正確的點座標時 　\(E(a_i)\ne 0\)(\(x=a_i\)代入錯誤位置多項式不為0(不符合)) 　\(b_i=f(a_i)\)(點座標\((a_i,b_i)\))符合\(f(x)\)多項式) (2)當\((a_i,b_i)\)為錯誤的點座標時 　\(E(a_i)=0\)(\(x=a_i\)代入錯誤位置多項式為0(符合)) 　\(b_i\ne f(a_i)\)(點座標\((a_i,b_i)\)不符合\(f(x)\)多項式) \(b_i=f(a_i)\)，兩邊同乘\(E(a_i)\)得到\(b_iE(a_i)=f(a_i)E(a_i)\) 設\(Q(a_i)=f(a_i)E(a_i)\)得到\(b_iE(a_i)=Q(a_i)\)，\(b_iE(a_i)-Q(a_i)=0\) (1)當\((a_i,b_i)\)為正確的點座標時(\(E(a_i)\ne 0,b_i=f(a_i)\)) 　\(b_iE(a_i)-Q(a_i)=b_iE(a_i)-f(a_i)E(a_i)=E(a_i)(b_i-f(a_i))=0\)等式成立 (2)當\((a_i,b_i)\)為錯誤的點座標時(\(E(a_i)=0,b_i\ne f(a_i)\)) 　\(b_iE(a_i)-Q(a_i)=b_iE(a_i)-f(a_i)E(a_i)=0(b_i-f(a_i))=0\)等式成立 代表點座標\((a_i,b_i)\)無論正確還是錯誤都符合\(b_iE(a_i)-Q(a_i)=0\) 將\(b_iE(a_i)-Q(a_i)=0\)，以\(\displaystyle E(a_i)=\sum_{i=0}^{e}e_i a_i^i\)，\(\displaystyle Q(a_i)=\sum_{i=0}^q q_ia_i^i\)展開 \(b_i(e_0+e_1a_i+e_2a_i^2+\ldots+e_ea_i^e)-(q_0+q_1a_i+q_2a_i^2+\ldots+q_qa_i^q)=0\) 其中\(q=n-e-1\)，又\(E(x)\)最高次方係數\(e_e=1\)，方程式改成 \(b_i(e_0+e_1a_i+e_2a_i^2+\ldots+e_{e_1}a_i^{e-1})-(q_0+q_1a_i+q_2a_i^2+\ldots+q_qa_i^q)=-b_ia_i^e\) 將各個點座標\((a_i,b_i)\)代入上式，解聯立方程組求\(e_0,e_1,\ldots,e_{e-1},q_0,q_2,\ldots,q_q\) \(E(x)\)有\(e\)個未知數，\(Q(x)=f(x)E(x)\)有\(k+e\)個未知數，需要\(n=e+(k+e)\)個方程式 該演算法從假設最大可能錯誤數\(\displaystyle e =\Bigg\lfloor\;\frac{n-k}{2}\Bigg\rfloor\;\)開始。如果方程式無法求解，則將\(e\)減1並重複此過程，直到聯立方程組可以求出惟一解或\(e\)降至0，表示沒有找到錯誤。 找到\(E(x)\)和\(Q(x)\)，解\(E(x)=0\)得到錯誤位置，計算\(\displaystyle f(x)=\frac{Q(x)}{E(x)}\)，秘密\(S=f(0)\)	有5個人聚在一起但不知道哪個人的子秘密是錯誤的 \((1,1494),(2,329),(3,123),(4,176),(5,1188)\)，(\((3,123)\)應為\((3,965)\)) \(\displaystyle e=\Bigg\lfloor\;\frac{5-3}{2}\Bigg\rfloor\;=1\)，最多可以修正1個錯誤 錯誤位置多項式\(E(x)=e_0+x\)，只有1個錯誤為1次多項式，\(e_0\)為錯誤點的\(x\)坐標 設\(Q(x)=E(x)f(x)\)次數為\(e+(k-1)=1+2=3\)次 \(Q(x)=q_0+q_1x+q_2x^2+q_3x^3\) 將\((a_i,b_i)=(1,1494),(2,329),(3,123),(4,176),(5,1188)\)代入\(b_i \cdot E(a_i)-Q(a_i)=0\) \(b_i(e_0+a_i)-(q_0+q_1a_1+q_2a_1^2+q_3a_1^3)\equiv 0\pmod{p}\) \(b_ie_0-(q_0+q_1a_1+q_2a_1^2+q_3a_1^3)\equiv -b_ia_i\pmod{p}\) \(\cases{1494e_0-(q_0+q_1\cdot 1+q_2 \cdot 1^2+q_3\cdot 1^3)\equiv -1494\cdot 1\cr 329e_0-(q_0+q_1\cdot 2+q_2 \cdot 2^2+q_3\cdot 2^3)\equiv -329\cdot 2\cr 123e_0-(q_0+q_1\cdot 3+q_2 \cdot 3^2+q_3\cdot 3^3)\equiv -123\cdot 3\cr 176e_0-(q_0+q_1\cdot 4+q_2 \cdot 4^2+q_3\cdot 4^3)\equiv -176\cdot 4\cr 1188e_0-(q_0+q_1\cdot 5+q_2 \cdot 5^2+q_3\cdot 5^3)\equiv -1188\cdot 5}\pmod{1613}\) 解聯立方程組，得到\(e_0=-3,q_0=-476,q_1=736,q_2=-116,q_3=94\) \(E(x)=-3+x\)，解\(E(x)=0\)，錯誤在\(x=3\) \(Q(x)=f(x)E(x)=f(x)(x-3)=-476+736x-116x^2+94x^3\pmod{1613}\) 使用綜合除法計算\(f(x)\) \(\frac{\matrix{94&-116&736&-476&|3\cr 　&282&498&3702&|　}}{\matrix{94&166&1234&|3226&　}}\) 餘式\(3226\equiv 0\pmod{1613}\)是整除的 \(f(x)=1234+166x+94x^2\pmod{1613}\) \(f(3)=1234+166\cdot 3+94\cdot 3^2=2578\equiv 965\pmod{1613}\) 正確的子秘密為\((3,965)\) 秘密\(S=f(0)=1234\)

要先載入interpol.mac才能使用lagrange指令
load("interpol.mac");
C:/maxima-5.47.0/share/maxima/5.47.0/share/numeric/interpol.mac

設定秘密S
S:1234;
\(1234\)

設定在GF(p)底下運算，其中p為質數
p:1613;
modulus:p;
\(1613\)
\(1613\)

需要3個人才能重組秘密，所以f(x)要為二次多項式
其中常數項為秘密S，一次項和二次項係數為隨機的整數
''S代表將1234代入S，若沒有''則為f(x):=S+166x+94x^2
f(x):=mod(''S+166*x+94*x^2,p);
\(f(x) :=mod(1234+166x+94x^2,p)\)

設定6個人要分享此秘密，計算f(x)上6個點座標分派給這6個人
shadows:create_list([x,f(x)],x,1,6);
\([[1,1494],[2,329],[3,965],[4,176],[5,1188],[6,775]]\)

假設第2,4,5位聚在一起要重組秘密S，利用拉格朗日插值多項式計算出f(x)
fx:lagrange([shadows[2],shadows[4],shadows[5]]);
fx:ratsimp(fx);
\(\displaystyle 396(x-4)(x-2)-88(x-5)(x-2)+\frac{329(x-5)(x-4)}{6}\)
\(94x^2+166x-379\)

其中常數項就是當初設定的祕密S
S:mod(ev(fx,x=0),p);
\(1234\)

使用者3的子秘密發生錯誤，應為[3,965]
shadows[3]:[3,123];
\([3,123]\)

有5個人聚在一起但不知道哪1個人的子秘密是錯誤的
Users:[1,2,3,4,5];
\([1,2,3,4,5]\)

錯誤位置多項式
E(x):=e0+x;
\(E(x) :=e0+x\)

Q(x)=f(x)E(x)多項式
Q(x):=q0+q1*x+q2*x^2+q3*x^3;
\(Q(x) :=q0+q1x+q2x^2+q3x^3\)

將5人的子秘密代入bi*E(ai)-Q(ai)=0
equations:[]$
for i in Users do
  (ai:shadows[ i ][1],/*x座標*/
   bi:shadows[ i ][2],/*y座標*/
   equations:append(equations,[bi*E(ai)-Q(ai)=0])
  )$
equations;
\([-q3-q2-q1-q0+1494(e0+1)=0,-8q3-4q2-2q1-q0+329(e0+2)=0,-27q3-9q2-3q1-q0+123(e0+3)=0,\)
\(-64q3-16q2-4q1-q0+176(e0+4)=0,-125q3-25q2-5q1-q0+1188(e0+5)=0]\)

聯立方程組以直式顯示
transpose(matrix(equations));
\(\left[\matrix{-q3-q2-q1-q0+1494(e0+1)=0\cr
-8q3-4q2-2q1-q0+329(e0+2)=0\cr
-27q3-9q2-3q1-q0+123(e0+3)=0\cr
-64q3-16q2-4q1-q0+176(e0+4)=0\cr
-125q3-25q2-5q1-q0+1188(e0+5)=0}\right]\)

解聯立方程組
solution:solve(equations,[e0,q0,q1,q2,q3]);
\([[e0=-3,q0=-476,q1=736,q2=-116,q3=94]]\)

將解代回E(x)和Q(x)
Ex:ev(E(x),solution[1]);
Qx:ev(Q(x),solution[1]);
\(x-3\)
\(94x^3-116x^2+736x-476\)

Q(x)除以E(x)得f(x)
fx: Qx/Ex;
fx:ratsimp(fx);
\(\displaystyle \frac{94x^3-116x^2+736x-476}{x-3}\)
\(94x^2+166x-379\)

解E(x)=0，得到錯誤位置
x:solve(Ex,x);
x:rhs(x[1]);
\([x=3]\)
\(3\)

算出第3位正確的子秘密
shadows[x]:[x,ev(fx,x=x)];
\([3,965]\)

秘密S=f(0)
S:mod(ev(fx,x=0),p);
\(1234\)

延續上一篇McEliece和Sarwate方案，提供另一個例子


要先載入interpol.mac才能使用lagrange指令
load("interpol.mac");
C:/maxima-5.47.0/share/maxima/5.47.0/share/numeric/interpol.mac

設定秘密S
(這個數字可自行修改，但S<p)
S:12345;
\(12345\)

設定在Fp底下運算，其中p為質數
p:65537;
modulus:p;
\(65537\)
\(65537\)

設定n個人共享秘密，至少要k個人才能重建秘密
(這兩個數字可自行修改，但n≥k)
n:8;
k:3;
\(8\)
\(3\)

最多可以修正Error個錯誤
Error:floor((n-k)/2);
\(2\)

隨機產生k-1次多項式，其中常數項為秘密S
f(x):=''(S+apply("+",create_list(random(p)*x^i,i,1,k-1)));
\(f(x) :=31816x^2+60108x+12345\)

產生n個點座標，將點座標mod p後分派給這n個人
shadows:create_list([i,mod(f(i),p)],i,1,n);
\([[1,38732],[2,63214],[3,20254],[4,40926],[5,59693],[6,11018],[7,25975],[8,39027]]\)

將順序打亂
shadows:random_permutation(shadows);
\([[7,25975],[3,20254],[1,38732],[5,59693],[6,11018],[8,39027],[2,63214],[4,40926]]\)

假設有k個人聚在一起要重建秘密
shadowk:sort(rest(shadows,-(n-k)));
\([[1,38732],[3,20254],[7,25975]]\)

利用拉格朗日插值多項式計算通過這k個點座標的k-1次多項式
fx:lagrange(shadowk);
fx:ratsimp(fx);
\(\displaystyle \frac{25975(x-3)(x-1)}{24}-\frac{10127(x-7)(x-1)}{4}+\frac{9683(x-7)(x-3)}{3}\)
\(31816x^2-5429x+12345\)

其中常數項為當初設定的祕密S
S:mod(ev(fx,x=0),p);
\(12345\)

需要(k+2*Error)個人聚在一起才能修正錯誤並重建秘密
shadows:rest(shadows,n-k-2*Error);
\([[3,20254],[1,38732],[5,59693],[6,11018],[8,39027],[2,63214],[4,40926]]\)

其中Error個人的子秘密是錯誤的
for i:1 thru Error do
  (print("假設第",shadows[ i ][1],"位使用者的子秘密是錯誤的，改成",shadows[ i ][2]:1111*i)
  )$
shadows:sort(shadows);
假設第3位使用者的子秘密是錯誤的，改成1111
假設第1位使用者的子秘密是錯誤的，改成2222
\([[1,2222],[2,63214],[3,1111],[4,40926],[5,59693],[6,11018],[8,39027]]\)

錯誤位置多項式E(x)
E(x):=''(apply("+",create_list(if i=Error then x^i else e[ i ]*x^i,i,0,Error)));
\(E(x) :=x^2+e_1x+e_0\)

Q(x)=f(x)E(x)多項式
Q(x):=''(apply("+",create_list(q[ i ]*x^i,i,0,k+Error-1)));
\(Q(x) :=q_4x^4+q_3x^3+q_2x^2+q_1x+q_0\)

將(k+2*Error)個子秘密代入bi*E(ai)-Q(ai)=0
equations:[]$
for shadow in shadows do
  (ai:shadow[1],/*x座標*/
   bi:shadow[2],/*y座標*/
    equations:append(equations,[bi*E(ai)-Q(ai)=0])
  )$
equations;
\(-q_4-q_3-q_2-q_1+2222(e_1+e_0+1)-q_0=0,-16q_4-8q_3-4q_2-2q_1+63214(2e_1+e_0+4)-q_0=0,\)
\(-81q_4-27q_3-9q_2-3q_1+1111(3e_1+e_0+9)-q_0=0,-256q_4-64q_3-16q_2-4q_1+40926(4e_1+e_0+16)-q_0=0,\)
\(-625q_4-125q_3-25q_2-5q_1+59693(5e_1+e_0+25)-q_0=0,-1296q_4-216q_3-36q_2-6q_1+11018(6e_1+e_0+36)-q_0=0,\)
\(-4096q_4-512q_3-64q_2-8q_1+39027(8e_1+e_0+64)-q_0=0\)

聯立方程組以直式顯示
transpose(matrix(equations));
\(\left[\matrix{-q_4-q_3-q_2-q_1+2222(e_1+e_0+1)-q_0=0\cr
-16q_4-8q_3-4q_2-2q_1+63214(2e_1+e_0+4)-q_0=0\cr
-81q_4-27q_3-9q_2-3q_1+1111(3e_1+e_0+9)-q_0=0\cr
-256q_4-64q_3-16q_2-4q_1+40926(4e_1+e_0+16)-q_0=0\cr
-625q_4-125q_3-25q_2-5q_1+59693(5e_1+e_0+25)-q_0=0\cr
-1296q_4-216q_3-36q_2-6q_1+11018(6e_1+e_0+36)-q_0=0\cr
-4096q_4-512q_3-64q_2-8q_1+39027(8e_1+e_0+64)-q_0=0}\right]\)

共有(k+2*Error)個未知數
variable:append(create_list(e[ i ],i,0,Error-1),
                          create_list(q[ i ],i,0,k+Error-1));
\([e_0,e_1,q_0,q_1,q_2,q_3,q_4]\)

解聯立方程組
solution:solve(equations,variable);
\([[e_0=3,e_1=-4,q_0=-28502,q_1=-130,q_2=-1565,q_3=-1619,q_4=31816]]\)

將解代回E(x)和Q(x)
Ex:subst(solution[1],E(x));
Qx:subst(solution[1],Q(x));
\(x^2-4x+3\)
\(31816x^4-1619x^3-1565x^2-130x-28502\)

Q(X)除以E(X)得f(x)
fx: Qx/Ex;
fx:ratsimp(fx);
\(\displaystyle \frac{31816x^4-1619x^3-1565x^2-130x-28502}{x^2-4x+3}\)
\(31816x^2-5429x+12345\)

解E(x)=0，得到錯誤位置
factor(Ex);
Errorx:solve(Ex,x);
\((x-3)(x-1)\)
\([x=1,x=3]\)

算出正確的子秘密
for i:1 thru Error do
  (x:rhs(Errorx[ i ]),
   print("第",x,"位使用者的子秘密是錯誤的，修正為f(",x,")=",mod(f(x),p))
  )$
第1位使用者的子秘密是錯誤的，修正為\(f(1)=38732\)
第3位使用者的子秘密是錯誤的，修正為\(f(3)=20254\)

秘密S=f(0)
S:mod(ev(fx,x=0),p);
\(12345\)

當要分享的秘密相當長時，每一份子秘密也會跟著變長使用上會造成不便，以Reed-Solomon編碼的另一種實現方式，犧牲些許安全性代價，來達到一定程度的資料壓縮。

原始Shamir秘密分享方案	秘密壓縮方案
假設分派者(Dealer)選定要共享的秘密S及一個質數p，滿足\( 0<S<p \)。分派者任意挑選一個\( k-1 \)次方的多項式\( f(x)=a_0+a_1x+a_2x^2+...+a_{k-1}x^{k-1} \)，滿足\( a_0=S \)，\( 0<a_1,a_2,…,a_{k-1}<p \)。 分派者利用\( f(x) \)產生n個子金匙\( (i,f(i)) \),\( i=1,2,...,n \)。每對\( (i,f(i)) \)可視為多項式\( f(x) \)在坐標平面上的一個點，由於\( f(x) \)為\( k-1 \)次方的多項式，因此k對或k對以上的點坐標可惟一決定\( f(x) \)，進而重建出秘密S。	假設\(b=(b_1,b_2,\ldots,b_k)\)是要分享的秘密，存在唯一一個Reed-solomon碼字(cdoeword)\(D\)，前\(k\)個就是密碼本身，即\(D_1=b_1,D_2=b_2,\ldots,D_k=b_k\)。事實上，\(D\)可以由Shamir方法的拉格朗日插值多項式或標準Reed-Solomon編碼演算法找到。只有剩下\(r-1-k\)個\(D_{k+1},\ldots,D_{r-1}\)可以分給參與者共享秘密，如前面所述，至少\(k\)個(未被竄改)才能還原秘密。
範例
設秘密\(S=1234567890\)非常長 再找比\(S\)還大的質數\(p=1234567907\) \(f(x)=1234567890+15618435x+38443541x^2\pmod{p}\) 常數項\(a_0=S\)，係數\(a_1,a_2\)為小於\(p\)的任意整數 \((1,f(1))=(1,54061959)\) \((2,f(2))=(2,185011017)\) \((3,f(3))=(3,392847157)\) \((4,f(4))=(4,677570379)\) \((5,f(5))=(5,1039180683)\) \((6,f(6))=(6,243110162)\) 每位使用者所拿到的子秘密幾乎和原始秘密長度相同 當三位使用者聚在一起，將各個子秘密\((3,f(3)),(4,f(4)),(6,f(6))\)利用拉格朗日插值多項式 \(\displaystyle f(x)=392847157\frac{(x-4)(x-6)}{(3-4)(3-6)}\) 　\(\displaystyle +677570379\frac{(x-3)(x-6)}{(4-3)(4-6)}\) 　\(\displaystyle +243110162\frac{(x-3)(x-4)}{(6-3)(6-4)}\pmod{p}\) \(f(x)=1234567890+15618435x+38443541x^2\pmod{p}\) 秘密\(S=f(0)=1234567890\)	將秘密\(1234567890\)拆成\(S=(0,1234),(1,567),(2,890)\) \(p=1613\) 利用拉格朗日插值多項式，產生通過\((0,1234),(1,567),(2,890)\)三點的二次多項式\(f(x)\) \(\displaystyle f(x)=1234\cdot \frac{(x-1)(x-2)}{(0-1)(0-2)}+567\cdot \frac{(x-0)(x-2)}{(1-0)(1-2)}+890\cdot \frac{(x-0)(x-1)}{(2-0)(2-1)}\pmod{1613}\) \(f(x)=1234+451x+495x^2\pmod{1613}\) 常數項\(a_0=S\)，係數\(a_1,a_2\)是根據拉格朗日插值多項式所產生的特定整數 \((3,f(3))=(3,590)\) \((4,f(4))=(4,1280)\) \((5,f(5))=(5,1347)\) \((6,f(6))=(6,791)\) \((7,f(7))=(7,1225)\) \((8,f(8))=(8,1036)\) 每位使用者所拿到的子秘密縮短許多 當三位使用者聚在一起，將各個子秘密\((3,f(3)),(4,f(4)),(6,f(6))\)利用拉格朗日插值多項式 \(\displaystyle f(x)=590\frac{(x-4)(x-6)}{(3-4)(3-6)}+1280\frac{(x-3)(x-6)}{(4-3)(4-6)}+791\frac{(x-3)(x-4)}{(6-3)(6-4)}\pmod{1613}\) \(f(x)=1234+451x+495x^2\pmod{1613}\) \(f(0)=1234\)，\(f(1)=567\)，\(f(2)=890\) 合併秘密\(S=1234567890\)
安全性
若已知2個子秘密\((3,392847157),(4,677570379)\) 代入\(f(x)=a_0+a_1x+a_2x^2\pmod{p}\)得 \(\cases{392847157=a_0+3a_1+9a_2\cr 677570379=a_0+4a_1+16a_2}\) 兩式相減得\(284723222\equiv a_1+7a_2\pmod{1234567907}\) \(a_1,a_2\)為隨機整數，知道\(a_1\)和\(a_2\)的關係式對於求\(a_0=S\)沒有幫助。	若已知2個子秘密\((3,590),(4,1280)\) 代入\(f(x)=a_0+a_1x+a_2x^2\pmod{p}\)得 \(\cases{590=a_0+3a_1+9a_2\cr 1280=a_0+4a_1+16a_2}\) 兩式相減得\(690\equiv a_1+7a_2\pmod{1613}\) \(a_1,a_2\)本身就是祕密的一部分，知道\(a_1\)和\(a_2\)的關係式對於秘密空間的複雜度被大大降低。

要先載入interpol.mac才能使用lagrange指令
(%i1)　load("interpol.mac");
(%o1)　C:/maxima-5.43.0/share/maxima/5.48.1/share/numeric/interpol.mac

設定非常長的秘密S
(%i2)　S:1234567890;
(%o2)　\(1234567890\)

設定在GF(p)底下運算，其中p為質數
(%i4)
p:1613;
modulus:p;
(%o3)　\(1613\)
(%o4)　\(1613\)

將長秘密分割，每個部份都小於p
(%i9)
SList:[]$
while S>p do
  (for i:2 thru floor(log(p)/log(10))+1 do
     (if mod(S,10^i)>p then
        (remainder:mod(S,10^(i-1)),
         S:floor(S/10^(i-1)),
         SList:append([remainder],SList)
        )
     )
  )$
print("將秘密S分割成",SList:append([S],SList))$
print("共有",SListLen:length(SList),"組")$
print("加上x座標",SList:makelist([i-1,SList[ i ]],i,1,SListLen))$
將秘密\(S\)分割成\([1234,567,890]\)
共有3組
加上\(x\)座標\([[0,1234],[1,567],[2,890]]\)

設定n個人共享秘密，至少要k個人才能重建秘密
(%i11)
n:6;
k:3;
(%o10)　\(6\)
(%o11)　\(3\)

利用拉格朗日插值多項式計算通過這SList個點座標的多項式
(%i12)　define(f(x),lagrange(SList));
(%o12)　\(f(x) :=445(x-1)x-567(x-2)x-617(1-x)(x-2)\)

設定6個人要分享此秘密，計算f(x)上6個點座標分派給這6個人
(%i13)　shadows:create_list([i,mod(f(i),p)],i,SListLen,n+SListLen-1);
(%o13)　\([[3,590],[4,1280],[5,1347],[6,791],[7,1225],[8,1036]]\)

假設任意k個人聚在一起要重組秘密S
(%i15)
shadows:random_permutation(shadows)$
shadowk:sort(rest(shadows,-(n-k)));
(%o15)　\([[3,590],[4,1280],[6,791]]\)

利用拉格朗日插值多項式計算出f(x)
(%i17)
fx:lagrange(shadowk);
fx:ratsimp(fx);
(%o16)　\(\displaystyle \frac{1225(x-6)(x-5)}{2}-791(x-7)(x-5)-\frac{1347(6-x)(x-7)}{2}\)
(%o17)　\(495x^2+451x-379\)

計算f(0),f(1),...,f(SListLen)
(%i18)　SList:create_list(mod(ev(fx,x=x),p),x,0,SListLen-1);
(%o18)　\([1234,567,890]\)

合併成秘密S
(%i19)　S:parse_string(apply(sconcat,map(string,SList)));
(%o19)　\(1234567890\)