第8章代数几何码

第8章代数几何码第8章代数几何码8.1代数几何的研究对象8.2仿射空间与仿射变换8.3射影空间与射影变换8.4在有限域上的仿射曲线与射影曲线8.5RS码与Goppa码8.6代数几何码的构成8.7代数曲线中的一些重要概念8.8Riemann-Roch定理8.9椭圆曲线码习题第8章代数几何码§8.1代数几何的研究对象代数几何是几何学中的一个重要研究领域，它研究平面代数曲线、空间代数曲线和代数曲面，更一般地，研究n维空间的代数簇。所谓代数簇，就是由一组代数方程所确定的点集以及由这些点集通过一定的规则导出的对象。例如，在普通直角坐标中，由代数方程F(x，y)＝0第8章代数几何码所决定的曲线即为平面代数曲线，这里F(x，y)是关于变量x，y的二元多项式。平面上的直线、圆锥曲线都是代数曲线，但是y-sinx=0所决定的正弦曲线便不是代数曲线。类似地，由三元多项式F(x，y，z)＝0第8章代数几何码决定的点集即为代数曲面。两个无关且相容的三元代数方程组F1(x，y，z)＝0F2(x，y，z)＝0所决定的点集，即为空间代数曲线。一般地，由n元代数方程组Fi(x1，x2，…，xn)＝0i＝1，2，…，m第8章代数几何码所决定的点集即为代数簇。研究一次曲线(直线)及一次曲面(平面)，以及二次曲线和曲面是普通解析几何中的内容。在上一世纪以前，代数几何是从研究三次及四次曲线及曲面的分类开始的。从19世纪末开始，人们才开始研究一般代数簇的系统结构。在代数几何的研究中采用拓扑学及抽象代数方法则是本世纪的事情。第8章代数几何码§8.2仿射空间与仿射变换定义8.2.1一个n维仿射空间AnK是点P，Q，R，…的集，满足:1°每一个有序点偶(P，Q)，恰有v∈VnK与之对应，记为PQ=v。2°每一个点P∈AnK及每一向量v∈VnK，恰有一点Q∈AnK使PQ＝v。第8章代数几何码3°对于AnK中任意三点P，Q，R，恒有PQ+QR＝PR设v∈VnK。由定义8.2.1之2°，对于每一点P∈AnK，恰有一点Q∈AnK使PQ＝v。由此定义了AnK上的一个映射Tv∶P→Q，PTv＝Q称此映射Tv为AnK上的一个平移(见图8-1)。第8章代数几何码图8-1AnK上的一个平移OQP第8章代数几何码图8–2AnK上的平移变换OQPb＋b第8章代数几何码定义8.2.2设αm为n维仿射空间AnK的非空子集，Sm为VnK的m维向量子空间。如果在AnK与VnK的相应关系下，αm恰好是相应于Sm的一个仿射空间，则称αm是AnK的一个m维仿射子空间。AnK的一维仿射子空间α1称为直线，二维仿射子空间α2称为平面。第8章代数几何码图8–3A2K中的直线OXP第8章代数几何码例如，考虑A2K中一条直线，它通过点P＝(p1，p2)，且该直线(作为一维仿射空间)相应的一维向量子空间以v＝(v1，v2)为基底，如图8-3所示。设X＝(x1，x2)为该直线上任意一点。于是PX必为该直线相应的一维向量子空间中的向量，因而可写成PX＝ρv(ρ∈K)。又因PX＝OX-OP＝(x1，x2)-(p1，p2)＝(x1-p1，x2-p2)，ρv=(ρv1，ρv2)，故(x1-p1，x2-p2)＝(ρv1，ρv2)第8章代数几何码由于v≠0(基向量)，不妨设v1≠0。于是，由x1-p1＝ρv1得111px将ρ代入x2-p2=ρv2中，便有v2x1-v1x2+(v1p2-v2p1)＝0令a1=v2，a2＝-v1，a0＝v1p2-v2p1，便有a1x1+a2x2+a0＝0(8.2.1)式中，a1、a2不全为0。第8章代数几何码反过来，每一个形如式(8.2.1)的一次方程均代表A2K中的一条直线。事实上，考虑满足方程式(8.2.1)的所有的点X＝(x1，x2)。由于a1，a2不全为0，不妨设a1≠0。于是x1＝-a-11(a0+a2x2)。选取P＝(-a-11a0，0)，v＝(-a2，a1)≠0，便有x＝(-a-11a0，0)+ρ(-a2，a1)＝p+ρvρ＝-a-11x2此处点x与点p为点X与P的位置向量。这表明方程式(8.2.1)代表通过点P且由向量v构成的直线。第8章代数几何码设e1，e2，…，en为n维向量空间VnK的基底。设{0，e1，e2，…，en}为相应的n维仿射空间Ank的坐标系。设X＝(x1，x2，…，xn)为Ank中任意一点。所谓仿射变换是指线性变换Y＝CX+b(8.2.2)式中nnnnnncccccccccC212222111211第8章代数几何码为域K上的非异矩阵，b＝(b1，…，bn)为AnK中一点。因此，仿射变换即为AnK上的非异齐次线性变换再加上平移。在变换式(8.2.2)之下，点X＝(x1，…，xn)变为点Y＝(y1，…，yn)。第8章代数几何码§8.3射影空间与射影变换引入n维仿射空间的出发点是n维向量空间。引入n维射影空间的出发点则是域K上的n+1维向量空间Vn+1K。设v，w∈Vn+1K。若存在r≠0(r∈K)使w＝rv，则称向量v与w等价。在等价的意义下，Vn+1K中的全部向量被分成等价类。零向量0构成由自身代表的一类。记为［0］。如果一个类中包含向量v，则此类用［v］代表。第8章代数几何码定义8.3.1在Vn+1K中所建立的每一个异于［0］的类称为射影点。所有射影点的全体所构成之集称为域K上的n维射影空间，记作PnK。因此，PnK中的点是Vn+1K中的一维子空间。Vn+1K中的二维子空间称为PnK中的射影直线，三维子空间称为PnK中的射影平面，m(m＞3)维子空间称为PnK中的(m-1)维超平面。在射影空间中可以引进齐次坐标的概念。第8章代数几何码设e1，…，en，en+1是Vn+1K的一个基底。于是PnK中每一点［X］皆可表为111111njjjnnnnexexexexX称(x1，…，xn，xn+1)为点［X］的射影齐次坐标。第8章代数几何码设［Y］=(y1，y2，y3)，［Z］＝(z1，z2，z3)为该直线上两点，［X］＝(x1，x2，x3)为该直线上任意一点。这表明相应的V3K中向量X，Y，Z线性相关，即存在不全为0的λ1，λ2，λ3使λ1X+λ2Y+λ3Z＝0。即齐次方程组：λ1x1+λ2y1+λ3z1＝0λ1x2+λ2y2+λ3z2＝0λ1x3+λ2y3+λ3z3＝0第8章代数几何码有非零解(λ1，λ2，λ3)。而这只有在条件0321321321zzzyyyxxx(8.3.1)第8章代数几何码之下才成立。而式(8.3.1)可写成u1x1+u2x2+u3x3＝0(8.3.2)式中u1=y2z3-y3z2u2=y3z1-y1z3u3=y1z2-y2z1并且u1，u2，u3不全为0(否则Y与Z将线性相关)。第8章代数几何码另一方面，若点［X］不在该直线上，则X，Y，Z必线性独立，因而行列式(8.3.1)必不为0，即［X］之坐标不满足式(8.3.2)。式(8.3.2)即为P2K中射影直线之一般方程。类似地，我们可建立射影空间中高次曲线的方程。射影空间中的曲线称为射影曲线。第8章代数几何码由于射影空间PnK中的第一类点包含了所有对应于仿射空间AnK中的点，同时在射影空间中还有第二种点，因此射影空间PnK可视为由仿射空间AnK中的点添加第二种点，即所谓虚点而获得的模型。由于所有虚点均对应于xn+1＝0的射影点，因此这种射影点位于一个射影超平面上，并且全部这种点对应于仿空间AnK的模像是(n-1)维线性子空间，即所谓(n-1)维流型。在A2K中是直线，在A3K中是平面，等等。在射影空间中，上述的虚点也称为无穷远点。第8章代数几何码§8.4在有限域上的仿射曲线与射影曲线设Fq(GF(q))代表q阶有限域。又设Fq代表Fq的代数闭包，即包含Fq的最小代数闭域。可以证明：mqmqFF1设F(x，y)代表Fq上的二元多项式，它在Fq上的全部根便定义为仿射平面A2(Fq)上的一条仿射曲线。多项式F(x，y)的次数称为该曲线的阶。第8章代数几何码定义8.4.1在仿射平面上A2(Fq)的点(a，b)，若a，b∈Fq，则称点(a，b)为A2(Fq)上的有理点。对于m次二元多项式F(x，y)，它定义了一条m阶仿射曲线，记为C。经过齐次化：zmF(x／z，y／z)便得到一个三元m次齐次多项式，记为F(x，y，z)。第8章代数几何码例如，考虑三次二元多项式F(x，y)＝y2-x2(x+1)它定义了仿射平面上一条三阶仿射曲线。经过齐次化：z3F(x／z，y／z)＝F(x，y，z)＝y2z-x3-x2z齐次化的过程相当于引进齐次坐标。一般，由m次二元多项式F(x，y)经过齐次化得到的三元m次齐次多项式F(x，y，z)，便定义了射影平面上的一条m阶代数曲线，称为m阶射影曲线。它是由仿射曲线C上的点添加某些无穷远点所构成的射影平面上的m阶代数曲线。第8章代数几何码反过来，每一条m阶射影曲线F(x，y，z)＝0也可通过非齐次化手续化为m阶仿射曲线F(x，y，1)＝0。例如五阶射影曲线F(x，y，z)＝x5+y5-z5＝0可化为F(x，y)＝x5+y5-1＝0这相当于由原来的m阶射影曲线去掉某些无穷远点所产生的m阶仿射曲线。第8章代数几何码定义8.4.2在射影平面P2(Fq)上的点(a，b，c)，当c≠0时，a／c，b／c∈Fq；当c＝0时(此时，a，b中至少有一不为0)，a／b∈Fq(b≠0)或b／a∈Fq(a≠0)；则称点(a，b，c)为P2(Fq)上的有理点。第8章代数几何码例8.1在P2(F4)上找出曲线y2z+yz2＝x3+x2z+xz2+z3(8.4.1)上的全部有理点。第8章代数几何码表8–1式(8.4.1)所示曲线上的全都有理点第8章代数几何码熟知，F4＝{0，1，α，β}，β＝α+1＝α2，经过计算，该曲线上的全部有理点共有9个，见表8-1。点Q(0，1，0)是无穷远点。式(8.4.1)所确定的曲线是亏格为1的代数曲线，称为椭圆曲线。椭圆曲线是编码理论中要讨论的重要曲线，以后我们会进一步解释。在实践上，真正算出给定曲线的全部有理点，或退一步，算出这些有理点的个数，均是相当困难的工作。如果多项式F(x，y)在Fq的任何扩域Fqm上均无异于常数的因式，则称相应的曲线为不可约曲线(既约曲线)。判断一条曲线的不可约性，也是一件相当困难的事情。第8章代数几何码§8.5RS码与Goppa码为了讨论一般的代数几何码，我们首先来回顾一下经典的RS码及Goppa码。正如定义7.3.1所述，RS码是Fq(q≠2)上码长为n=q-1的本原BCH码，该码的生成多项式为)()(11idixxg第8章代数几何码式中，α为Fq的本原域元素。RS码是码长为n(=q-1)，信息位数为n-d+1，最小距离为d的极大最小距离可分码［n，n-d+1，d］，亦即MDS码。像所有线性码一样，对于［n，n-d+1，d］RS码增加一个全校验位后，便成为扩展RS码。它是码长为n+1(=q)，信息位数仍为n-d+1的［n+1，n-d+1］码。由定理7.3.1，这个码的最小距离为d+1，因而扩展RS码仍为MDS码。第8章代数几何码我们现在遵循里德与索洛蒙原来的编码方法，也就是用M-S多项式构造RS码的方法来建立扩展RS码。为了方便，我们取n=q。Fq中的元素记成αi＝αi0≤i≤q-2式中，α为Fq的本原域元素。令L＝{f∈Fq［x］f≤k-1}k＜n我们定义一个码C为C＝{(f(α0)，f(α1)，…，f(0))｜f∈L}(8.5.1)第8章代数几何码正如§7.3中所指出的码C是用频域方法编出的扩展RS码，码长n=q，信息位数为k，即L(作为线性空间)的维数。又因L中的多项式次数≤k-1，故不可能多于k-1个零点，从而码C的最小距离dm≥n-k+1。另一方面，推论3.2.1指出：任何线性码的最小距离至多为该码的校验位数加1，即dm≤n-k+1因此，dm=n-k+1。这表明码C是［n，k，n-k+1］线性码，亦即MDS码。第8章代