[課業] 網路,漢明距離,資料結構,radixsort排序
在一個通訊系統中，我們擬將0000到1111等16組不同二進位(binary)訊息傳遞出去。而每
一個訊息將搭配一組三位元(3-bit)的CRC(cyclic redundancy check)。其中generator
polynomial為x3＋x2＋1。試問：
1.請導出右列四個訊息的check bits：0000 0001 0010 1111
利用模數(modulo)2除法計算出餘數
G(x)為1101，xrM(x)為0000000 0001000 0010000 1111000
message check bits
0000 000
0001 101
0010 111
1111 111
2.定義「Hamming distance」。並算出上一小題中各個transmitted codeword的
Hamming distance值。
漢明距離(Hamming distance)的定義：給予兩個任何的字碼，10001001和10110001，即可
決定有多少個相對位元是不一樣的。在此例中，有三個位元不同。要決定有多少個位元不
同，只需將exclusive OR運算加諸於兩個字碼就可以，並在結果中計算有多個為1的位元
。例如：
10001001
Xor 10110001
00111000
兩個字碼中不同位元值的數目稱為漢明距離(Hamming distance) 。它的重要性在於如果
有兩個字碼的漢明距離為d的話，就需要d的單一位元錯誤已將其中一個字碼轉換為另一個
。
Hamming Distance 是指兩個 codewords 之間相異的位元數。
0000000 0001101 0010111 1111111
0000000 3 4 7
0001101 3 3 4
0010111 4 3 3
1111111 7 4 3
3.請回答：當1100此訊息被傳遞時，如何偵測出single-bit error及double-bit error？
將接收到的 message 1100 的 M(x)=x3+x2 與 check bits C(x)，以 module-2 的除法
，除以 generator polynomial G(x)，即 M(x)*x3+C(x) 除以 G(x)，若餘數 R(x) 為 0
，則表示接收到的 message 是正確的；反之，則表示有錯誤發生。
4.請舉出一個無效的(invalid)codeword。當此invalid codeword被接收後，上述的CRC
機制無法偵測其正確與否。
上述的 CRC 機制，其 codewords 之間的最小漢明距離為 3，因此發生 3-bit error時，
即無法找出其錯誤，例如 0010111 若錯了三個 bits 成為 1111111 時，無法查出其錯誤
。
這是在網路上找到的詳解,1.2題沒問題
第三題要偵測出單一位元與兩個位元錯誤我知道是要用漢明距離為3吧
但是不是要一堆資料漢明距離互為3的話才可以偵測出嗎~?
這題目是不是怪怪的呢~? 還是?
第四題應該是隨便找一組4位元數據補3個零然後除以generator再加上餘數就可以了吧?
四、假設輸入X1，X2 . .，Xm個正整數且每個數之值介於1到n^2之間。
試寫一排序(sort)這m個數字的演算法，演算法必須滿足O(m+n)的時間複雜度。
(20分)
這題我知道是要用radix sort
但是時間複雜度是要O(m+n)
總時間為把每個資料丟進桶子的時間加上桶子的處理分配時間,
如果是用鏈結串列就是把每個桶子串在一起的時間
問題是桶子要有n^2個,他時間複雜要求要O(m+n)
難道有更好的方法嗎~?
附上演算法http://ideone.com/kTt6ur
這演算法是用陣列寫的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.246.69