數學怎麼讓溝通無礙？錯誤更正碼｜通信大解密📱｜第四部 通信的技術
HTML-код
- Опубликовано: 28 сен 2024
- 錯誤更正碼看起來是一項艱深的技術，以威老師常看到很多學生論文反覆讀了好多次，還是像在看天書，因為它的數學推導很多、很複雜。必須同時具備一定的數學能力和通信知識，才能學會這項技術。
日常生活中，當我們與人溝通時，說話者想辦法「說得更清楚」。換句話說，錯誤更正碼是「減少通信錯誤」的技術，也就是減少溝通誤會，清楚地表達傳輸端的意思。比方說，有時候在人多吵雜的餐廳，會提高音量說話，確保對方能聽清楚，這就相當於無線通信在干擾很多的地方，自動增加傳輸功率，增加信號與雜訊比。有時候，會選擇把一句話重複多說幾次，重複講一樣的話，有一種錯誤更正碼，稱為重複碼（repetition code）。概念上是把一樣的資訊重複多傳幾次，確保接收端至少能聽到一次。但重複傳一樣的，很快人們就會發現不太有用。有可能對方不理解「我沒有」是什麼意思，是你沒有吃飯，但你亂丟東西？還是你沒有亂丟東西？在通信系統中，傳輸的資料，是你想要表達的話，我們稱為未編碼的位元或資訊位元（uncoded bits, information bits），經過編碼器進行錯誤更正碼，我們會稱編碼後的位元(coded bit)，或碼字（codeword）。這邊特別講一點，這裡的編碼不是為了資訊安全的理由，不是為了保護資料不要被別人竊取，而是為了保護資料能在傳輸中不會遺失。編碼利用「重複說」跟「換句話再說」提升傳輸可靠度。對工程師來說，凡事都是取捨（trade-off），得到了某些，就會失去某些。錯誤更正碼得到可靠度，是犧牲了什麼呢？
答案是傳輸速率。以重複說來看，如果重複一次，傳輸速率就直接掉一半，原本一秒傳100個位元，全部都是information bits，現在變成一秒內只能有50個information bits的資料，重複傳遞2次；如果重複4次，那傳輸速率直接變1/4倍。換句話說，這樣的編碼技術會降低傳輸速率。不過有人可能會想到，人類的換句話說也能用「更少的字說完」，所以搞不好可以更快說完，傳輸速率更高，對應的技術是「壓縮」，比方說「想要請問一下，你們這個店裡，如果要上網的話，Wi-Fi的那個，帳號密碼我想登入的話，去哪裡找？」，就可以直接精簡成「請問Wi-Fi帳密？」這就是壓縮。壓縮可以少傳一些位元，等效提升傳輸速率。錯誤更正碼不是為了這個目的而設計，它完全不考慮壓縮，永遠是假設我今天收到的資訊就已經是最精簡的「請問Wi-Fi帳密？」，我就是要保護它，犧牲一些傳輸速率，多說幾個字，提升傳輸準確度。只能說人的大腦還是很厲害，能同時去處理壓縮、錯誤更正碼等功能，電腦還是得明確分工，確定目標後，再各自設計每個對應的演算法。講完錯誤更正碼的直觀概念後，現在來加入一些數學講「距離」。兩點之間連成一條直線，直線的長度是多少，就是距離。舉例，如果是座標平面上兩個點，座標分別是(1,2)跟(4,6)，我們就會去算4-1的平方加上6-2的平方，再開根號，答案是5，兩點的距離是5。如果你不了解這公式怎麼來的，可以再找出一個點(4,2)，然後它們形成一個(3,4,5)的直角三角形，(1,2)跟(4,6)的距離就是斜邊長度，這是畢氏定理。既然我們刻意把距離前面加了歐基里德，大家可能就會知道，所以有不是歐基里德距離的距離嗎？沒錯，在以二進為為主的通信系統裡，我們還有另一種距離叫做 #漢明距離（Hamming distance），為了紀念工程師、數學家理查·漢明，他在錯誤更正碼領域，或是更廣一點通信領域應該是無人不知。漢明距離比較的是兩組二進位數據裡，有幾個位元不一樣。舉例來說，如果今天你傳遞的資料是1111，但收到的是1101，這兩筆數據在第三個位元不一樣，所以它們的漢明距離就是1，但如果收到的是1001，漢明距離就是2。如果收到0000，這個漢明距離就很大了，是4。所以你會看到，漢明距離的計算方式不難，就像那種小學生玩大家來找碴，數數看兩邊有哪些不一樣，有幾個位元不一樣，漢明距離就是多少。漢明距離的價值是「量化」了差異性：漢明距離越大，兩組資料差異越大；漢明距離越小，兩組距離差異越小。你也可以反過來說，是量化了相似度（similarity），漢明距離越小，相似度越大，兩者越相似，越容易被搞混。傳輸時，每個位元都有可能受到干擾而再接收端被判斷錯誤。通常我們會比較容易判斷錯成「漢明距離小」的那些字串，而不是那些漢明距離大的字串，因為你比較有可能是只錯一兩個位元，一口氣錯很多位元的機率比較低。這是剛說的，傳輸時，因為通道的干擾，接收端有可能會搞混成相似度比較大，也就是漢明距離比較小的字串。
錯誤更正碼一個重要概念是，傳輸時每一組碼字，也就是編碼過後的資料，要盡量長得不一樣，這樣他們就比較不容易被誤認。好比今天打造一個動物園。如果你故意放海豹、海獅；鱷魚、短吻鱷；美洲駝、羊駝。那大家一定就超困擾，告示牌擺了也搞不清楚誰是誰，一直認錯。但如果你這幾對都只放一種類型，搭配告示牌，大家應該就能很清楚知道噢原來你放的是海獅、鱷魚、羊駝。不會有人把海豹誤認為是羊駝，因為差太遠了。回到通信技術，簡單地說如果我們今天的資料是1個位元，那用3個位元作為我們的碼字。我們用001代表0，110代表1，就會是比起用000代表0，100代表1要來得更好。因為001跟110比較不容易被辨認錯誤，漢明距離高達三，任意兩個位元錯都沒關係。如果你用000跟100，漢明距離只有1，那第一個位元一錯，整個就會亂掉了。簡單說編碼的過程，其實就是想把資料位元的「各種可能組合」，對應到「漢明距離差距很大」的各式各樣碼字。各種可能組合要補充說明一下，人類說話有無限多種可能，但通信系統只要你給定傳輸的位元數量，資料是有限的。假設3個位元，那就一定是000、001、010、011、100、101、110、111總計八種，2的三次方。如果是N個位元，就是2的N次方。而編碼會用到更多個位元，假設剛剛的傳輸3個位元，我編碼後的碼字有5個位元，那我理論上就有2的五次方這麼多種碼字。可是我不需要這麼多啊，因為我只要能傳遞8個位元就好，那是不是我就可以把一些碼字，我選了海豹，就把海獅放生，選了00000，就不要再選00001或1000。32組可能性中，我可以捨棄掉24個5位元的碼字，只要留下8個就好了。如此一來，剩下的碼字彼此之間的漢明距離就會變大。通常傳輸的資料，因為所有組合都會發生，最小漢明距離都是1。那只要碼字的最小漢明距離，也就是任意兩組碼字它們的漢明距離，的最小值，大於1。傳輸品質就會提升，那最小漢明距離越大，效能就會越好。這個最佳化的概念也稱之為最大化最小值（max min），有點像是經濟政策有很多種嘛，提可以提升全民的整體收入，這稱之為最大化總和（max sum）；也可以說我的社會公平性要做到很好，目標是要讓最貧窮的人收入持續增加，這就是max min。那在錯誤更正碼的設計裡，我們就不是要讓所有coedwords彼此之間的漢明距離加總最大，而是要讓最小的漢明距離，數值越大越好。
#通信大解密 #生活中的通信 #錯誤更正碼 #漢明距離
原來錯誤更正碼是很重要的通信技術之一
雖然不是唸通訊相關的科系，但有做過通訊裝置的產品，spec.上都一定會規範錯誤更正碼或檢查碼來確認收到的封包內容是正確的，否則拿到錯誤的資料，輕則小小的glitch，嚴重的直接當機
溝通不良時更正再多次也沒用😅
電路也會考慮資料的特性，有些架構在在連續筆數的0或1時，工作狀態就會開始飄掉，因此會有編碼刻意的來降低同位準連續筆數的數量，盡量均勻分散1與0，也就是降低低頻成分，提升高頻成分，使得電路可以保持適切的工作條件，但一樣也要拿information bit來trade off
為什麼很多一樣的就會飄掉？
@@jimmychen4308 DC block，DC偏壓定義電路工作點，RF訊號交流耦合進來，連續的資料位準會充電或放電導致位準飄移，連續的資料越長，形同提供充電放電的時間越長，飄移越大，下次轉態訊號就會踩在飄移點後再位移一個資料擺幅。
@@jimmychen4308在AIC或者RFIC中會有RC或LC構成的偏壓電路，為DC bolck或choke電路，這東西可決定放大器的工作點，以及將交流訊號耦合進來，因此可以想像到輸入訊號必須踩在直流工作點，也就有兩條路徑，AC及DC路徑，而輸入訊號的電壓與週期會影響電容充放電，電容必須靠時變來傳遞資訊，低頻率的訊號，也就是長時間不變的訊號，就會影響電容電壓位準，可能被充電或放電導致放大器偏壓跑掉。