21 123
發新話題
打印

用Maxima學密碼學-秘密分享

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.
http://citeseerx.ist.psu.edu/vie ... p=rep1&type=pdf

但糾錯編碼又是另外一個領域的東西,所以只提供三篇文章簡介什麼是糾錯編碼,沒有maxima範例。



錯誤更正碼簡介
http://w3.math.sinica.edu.tw/math_media/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

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








字母編碼字母編碼字母編碼
a00001j01010s10011
b00010k01011t10100
c00011l01100u10101
d00100m01101v10110
e00101n01110w10111
f00110o01111x11000
g00111p10000y11001
h01000q10001z11010
i01001r10010


  由收到的資料解讀,每五個數字一組,解讀後得出「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年。

---------------------------

錯誤訊息的偵測與修正


賴紹正


為什麼條碼機可以正確地讀出你購買的商品價錢?為什麼稍稍刮損的音樂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

TOP

 21 123
發新話題