在一个通讯系统中，我们拟将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