[其他] 離散兩題

看板Math作者 (俊偉)時間3年前 (2020/10/08 16:55), 編輯推噓2(2推 0噓 26→)
留言28則, 2人參與, 3年前最新討論串2/5 (看更多)
題目1:https://imgur.com/a/bwIe3cc 不需要知道(a)(b)(c)部分 跟(d)(e)無關 (d)部分我有證出後半段 想問要如何證明前半段 Hamming distance between any two codewords in RS[5,3] is at least 3 (e)部分沒什麼想法 題目的max Hamming distance = m-n+1是typo 應該是min Hamming distance = m-n+1 題目2:https://imgur.com/a/pJud5MX 題目裡的Maru還沒開始比 他贏第一場就拿1分 之後贏第i場就拿i分 (a)部分沒甚麼問題 (b)部分 我的想法是把分數i∈{1,2,...,10} 看作x_1+2x_2+3x_3+...+10x_10 > 27 0 <= x_i <= 1 但是不知道怎麼解含係數!= 1的不等式 我只解過x_1+x_2+...x_n = k這種的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.187.128 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1602147303.A.1B1.html
→
10/08 22:13, 3年前 , 1F
讓F是指定的finite field 給定u1,u2在F^3中 並令P1,
10/08 22:13, 1F
→
10/08 22:15, 3年前 , 2F
P2為其相對應的polynomials 則Hamming distance為
10/08 22:15, 2F
→
10/08 22:17, 3年前 , 3F
((P1-P2)(a0),(P1-P2)(a1),...,(P1-P2)(a5))的非零
10/08 22:17, 3F
→
10/08 22:18, 3年前 , 4F
個數 注意到(P1-P2)是一個degree小於等於2的多項式
10/08 22:18, 4F
→
10/08 22:20, 3年前 , 5F
所以最多兩個零根 故至少三個非零
10/08 22:20, 5F
→
10/08 22:22, 3年前 , 6F
至於(e) 你的Decode(*)的定義或者所採用的演算法是
10/08 22:22, 6F
→
10/08 22:24, 3年前 , 7F
啥? 因為一般的error correction code的decoding
10/08 22:24, 7F
→
10/08 22:25, 3年前 , 8F
function就是要滿足圖中的式子 並以此來找decode的
10/08 22:25, 8F
→
10/08 22:28, 3年前 , 9F
算法 (一般來說 如果我們接收到錯誤的代碼C' 我們糾
10/08 22:28, 9F
→
10/08 22:28, 3年前 , 10F
正錯誤的方法 就是去找Hamming distance最近的
10/08 22:28, 10F
→
10/08 22:29, 3年前 , 11F
codeword 再以此decording)
10/08 22:29, 11F
→
10/08 22:35, 3年前 , 12F
至於題目2 我目前也沒有有效率的算法 不過可以用下
10/08 22:35, 12F
→
10/08 22:40, 3年前 , 13F
列遞迴函數的方式解 令F(n,m)為"從1到n中至少取一個
10/08 22:40, 13F
→
10/08 22:41, 3年前 , 14F
且其總和小於等於m"的方法數 則我們有
10/08 22:41, 14F
→
10/08 22:43, 3年前 , 15F
F(1,k)=1 for all k in N
10/08 22:43, 15F
→
10/08 22:45, 3年前 , 16F
when m>n, F(n,m)=F(n-1,m)+F(n-1,m-n)+1
10/08 22:45, 16F
→
10/08 22:47, 3年前 , 17F
when m=n, F(n,m)=F(n-1,m)+1
10/08 22:47, 17F
→
10/08 22:49, 3年前 , 18F
when m<n, F(n,m)=F(n-1,m)
10/08 22:49, 18F
→
10/08 22:50, 3年前 , 19F
則所求為 1023-F(10,27) 至少可以跑程式 冏
10/08 22:50, 19F
→
10/09 15:27, 3年前 , 20F
題目2的(b)根本不用上面這麼麻煩 XD 當我們從{1,2,
10/09 15:27, 20F
→
10/09 15:28, 3年前 , 21F
3,...,10}中取一些數出來總和大於27時 剩下來的數總
10/09 15:28, 21F
→
10/09 15:29, 3年前 , 22F
和就會小於等於27 反之亦然 也就是說我們可以在1024
10/09 15:29, 22F
→
10/09 15:30, 3年前 , 23F
個子集合中兩兩湊對 所以總共有1024/2=512種方法數
10/09 15:30, 23F
→
10/09 15:34, 3年前 , 24F
這裡湊對的方式就是子集合和他的補集
10/09 15:34, 24F
→
10/09 15:34, 3年前 , 25F
所以27這個數字是特別挑過的 (28是1到55的中間)
10/09 15:34, 25F
→
10/09 19:33, 3年前 , 26F
對，我後來看到程式結果也想到這樣XD
10/09 19:33, 26F
推
10/09 20:35, 3年前 , 27F
XD 我也是
10/09 20:35, 27F
推
10/09 20:41, 3年前 , 28F
這是個很好的警惕 先跑程式看看答案再說 XD
10/09 20:41, 28F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VVjFd6n (Math)
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VVjFd6n (Math)