[其他] 離散兩題

看板Math作者 (俊偉)時間3年前 (2020/10/07 18:03), 編輯推噓0(0推 0噓 22→)
留言22則, 2人參與, 3年前最新討論串1/5 (看更多)
題目: https://imgur.com/a/6OaKvcF 第一題想法: (不知道對不對) 假設2 polynomials with degree n-1 P1(x)=c{n-1}x^{n-1}+c{n-2}x^{n-2}+...+c{0} P2(x)=d{n-1}x^{n-1}+d{n-2}x^{n-2}+...+d{0} 假設兩constants a,b 推得aP1(x)+bP2(x) -> (aP1+bP2)(x) 就算證明完成? 第二題: 沒什想法，也不知道理解對不對 沿用前一題的兩個polynomials 做element-wise product ->係數會變成[c{n-1}d{n-1}, c{n-2}d{n-2}, ..., c{0}d{0}] 這樣message不是還是length n嗎? 如果是做P=P1(x)*P2(x) deg(P)=deg(P1(x))+deg(P2(x))=(n-1)+(n-1)=2n-2 length 也只有2n-1，也不是2n -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.187.128 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1602065038.A.EC8.html
→
10/08 01:38, 3年前 , 1F
第一題差不多就是原po的想法吧 令F=GF(p)
10/08 01:38, 1F
→
10/08 01:45, 3年前 , 2F
C:F^n→F^m是encoding function 則對於u1=(c{0},...
10/08 01:45, 2F
→
10/08 01:47, 3年前 , 3F
c{n-1}) 我們有 C(u1)=(P1(0),P1(1),...,P1(m-1))
10/08 01:47, 3F
→
10/08 01:50, 3年前 , 4F
其中P1(x)=c{n-1}x^{n-1}+c{n-2}x^{n-2}+...+c{0}
10/08 01:50, 4F
→
10/08 01:52, 3年前 , 5F
所以用原po的想法就可以證
10/08 01:52, 5F
→
10/08 01:53, 3年前 , 6F
a*C(u1) + b*C(u2) = C(a*u1+b*u2)
10/08 01:53, 6F
→
10/08 01:56, 3年前 , 7F
這裡a Reed–Solomon codeword是指an image of C
10/08 01:56, 7F
→
10/08 02:03, 3年前 , 8F
第二題應該就是用原po最後一段的想法 做類似於上面
10/08 02:03, 8F
→
10/08 02:05, 3年前 , 9F
的證明 雖然感覺有點奇怪 不過deg 2n-2的polynomial
10/08 02:05, 9F
→
10/08 02:09, 3年前 , 10F
的確就是degree小於2n的polynomial (當我們考慮
10/08 02:09, 10F
→
10/08 02:10, 3年前 , 11F
Messages的空間 F^{2n}時 對於裡面的元素 如果我們
10/08 02:10, 11F
→
10/08 02:11, 3年前 , 12F
將其視為多項式的係數時 我們會得到degree小於2n的
10/08 02:11, 12F
→
10/08 02:13, 3年前 , 13F
所有多項式所形成的空間)
10/08 02:13, 13F
→
10/08 02:15, 3年前 , 14F
更精確的說 如果令C':F^{2n}→F^m是encoding func
10/08 02:15, 14F
→
10/08 02:17, 3年前 , 15F
並令&為兩個blocks的element-wise product
10/08 02:17, 15F
→
10/08 02:19, 3年前 , 16F
則對任何u1,u2在F^n中 的確存在v在F^{2n}中使得
10/08 02:19, 16F
→
10/08 02:22, 3年前 , 17F
C(u1) & C(u2) = C'(v) 故C(u1) & C(u2)的確在
10/08 02:22, 17F
→
10/08 02:22, 3年前 , 18F
RS[m,2n]中
10/08 02:22, 18F
→
10/08 04:15, 3年前 , 19F
真的是大神
10/08 04:15, 19F
→
10/09 06:32, 3年前 , 20F
教授說是typo, RS[m,2n-1]才是對的，所以想法正確
10/09 06:32, 20F
→
10/09 15:32, 3年前 , 21F
XD 其實RS[m,2n-1]的codeword也是RS[m,2n]的
10/09 15:32, 21F
→
10/09 15:33, 3年前 , 22F
cordword 感覺也不需要特別說是typo XD
10/09 15:33, 22F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VVPAEx8 (Math)
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VVPAEx8 (Math)