作者LiquidTLO (俊偉)
看板Math
標題[其他] 離散兩題
時間Wed Oct 7 18:03:54 2020
題目:
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://webptt.com/m.aspx?n=bbs/Math/M.1602065038.A.EC8.html
1F：→ hwanger : 第一題差不多就是原po的想法吧 令F=GF(p) 10/08 01:38
2F：→ hwanger : C:F^n→F^m是encoding function 則對於u1=(c{0},... 10/08 01:45
3F：→ hwanger : c{n-1}) 我們有 C(u1)=(P1(0),P1(1),...,P1(m-1)) 10/08 01:47
4F：→ hwanger : 其中P1(x)=c{n-1}x^{n-1}+c{n-2}x^{n-2}+...+c{0} 10/08 01:50
5F：→ hwanger : 所以用原po的想法就可以證 10/08 01:52
6F：→ hwanger : a*C(u1) + b*C(u2) = C(a*u1+b*u2) 10/08 01:53
7F：→ hwanger : 這裡a Reed–Solomon codeword是指an image of C 10/08 01:56
8F：→ hwanger : 第二題應該就是用原po最後一段的想法 做類似於上面 10/08 02:03
9F：→ hwanger : 的證明 雖然感覺有點奇怪 不過deg 2n-2的polynomial 10/08 02:05
10F：→ hwanger : 的確就是degree小於2n的polynomial (當我們考慮 10/08 02:09
11F：→ hwanger : Messages的空間 F^{2n}時 對於裡面的元素 如果我們 10/08 02:10
12F：→ hwanger : 將其視為多項式的係數時 我們會得到degree小於2n的 10/08 02:11
13F：→ hwanger : 所有多項式所形成的空間) 10/08 02:13
14F：→ hwanger : 更精確的說 如果令C':F^{2n}→F^m是encoding func 10/08 02:15
15F：→ hwanger : 並令&為兩個blocks的element-wise product 10/08 02:17
16F：→ hwanger : 則對任何u1,u2在F^n中 的確存在v在F^{2n}中使得 10/08 02:19
17F：→ hwanger : C(u1) & C(u2) = C'(v) 故C(u1) & C(u2)的確在 10/08 02:22
18F：→ hwanger : RS[m,2n]中 10/08 02:22
19F：→ LiquidTLO : 真的是大神 10/08 04:15
20F：→ LiquidTLO : 教授說是typo, RS[m,2n-1]才是對的，所以想法正確 10/09 06:32
21F：→ hwanger : XD 其實RS[m,2n-1]的codeword也是RS[m,2n]的 10/09 15:32
22F：→ hwanger : cordword 感覺也不需要特別說是typo XD 10/09 15:33