作者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/cn.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