編碼技術(shù)數(shù)學基礎

編碼技術(shù)數(shù)學基礎第一頁，共十九頁，編輯于2023年，星期五簡單基礎最大公約數(shù)GCD最小公倍數(shù)LCM同余和剩余類同余類的加減乘除第二頁，共十九頁，編輯于2023年，星期五群一個系統(tǒng)、一種數(shù)學系統(tǒng)、一種代數(shù)結(jié)構(gòu)非空集合G和G上定義的一種運算“·”，并滿足條件：封閉性，任意兩個集合中元素的運算結(jié)果仍是集合的元素,即任意a,b∈G，有a·b∈G結(jié)合律，(a·b)·c=a·(b·c)存在單位元e對任意集合中元素a，有逆元a-1，使得a·a-1=a-1·a=e規(guī)定：n個a的運算記為a·a·…·a=an，a0=e滿足交換律的群叫交換群或Abel群第三頁，共十九頁，編輯于2023年，星期五群的若干定理及性質(zhì)群中單位元唯一，每個元素的逆元唯一群中元素的個數(shù)稱為群的階循環(huán)群：群中每個元素都是a的某個整數(shù)次冪an，稱該群有a生成，a是該群的生成元使得an=1的最小正整數(shù)n，稱為a的級n階循環(huán)群中，任意元素的級是n的某個因子n階循環(huán)群中，每個n級的元素都稱為n次單位原根單位原根的個數(shù)是歐拉數(shù)第四頁，共十九頁，編輯于2023年，星期五域非空集合F和F上定義的加法和乘法兩種運算，滿足條件：F中全體元素構(gòu)成交換加群，有加法單位元0，a的逆元稱為負元，記為-aF中全體非零元素構(gòu)成交換乘群，乘法單位元為1加法和乘法之間滿足分配律記n個a相加為na，n個a相乘為an，a0=1域中元素個數(shù)q稱為階，若元素個數(shù)有限，則稱為有限域或伽羅華域GF(q),Fq第五頁，共十九頁，編輯于2023年，星期五子群，陪集若H是群G的非空子集，且依G上的運算構(gòu)成群，則H是G的子群G有兩個平凡子群，自身和單位元構(gòu)成的群，其他非平凡子群稱為真子群對G的子群H，構(gòu)建g·H={g·h1,g·h2,…}，稱為左陪集，構(gòu)建

H·g={h1·g,h2·

g,…}，稱為右陪集，陪集中最左邊的第一個稱為陪集首交換群中左陪集等于右陪集第六頁，共十九頁，編輯于2023年，星期五陪集的性質(zhì)G關(guān)于H的所有陪集構(gòu)成G的一個劃分，即所有陪集的并就是G任意兩個陪集的任意元素都不同陪集的大小是H的階，所有陪集大小相同第七頁，共十九頁，編輯于2023年，星期五有限域上的多項式系數(shù)取自Fq上的x的多項式稱為有限域上的多項式，全體這類多項式的集合記為GF(q)[x]或Fq[x]全體系數(shù)都為0的零多項式，記為0，x的最高次項為1的多項式稱為首一多項式不可約多項式：除了常數(shù)和本身，沒有其他非零次多項式為因子第八頁，共十九頁，編輯于2023年，星期五多項式的概念次數(shù)、根多項式的歐幾里得除法多項式互素多項式的最大公因式GCD多項式的最小公倍式LCM多項式的同余和剩余類第九頁，共十九頁，編輯于2023年，星期五有限域的乘法結(jié)構(gòu)以素數(shù)q為模的整數(shù)剩余類構(gòu)成q階有限域GF(q)；以GF(q)上m次首一不可約多項式為模的多項式剩余類構(gòu)成qm階有限域GF(qm)有限域GF(q)中非零元素構(gòu)成q-1階乘群(循環(huán)群)，其中存在一個生成元，級為q-1，是q-1次單位原根，稱為本原元GF(q)中q-1個非零元素都是xq-1-1=0的根，反之xq-1-1=0的每個根都在GF(q)中，即任意元素的q-1次方都為1第十頁，共十九頁，編輯于2023年，星期五有限域的加法結(jié)構(gòu)滿足n個1（乘法單位元）相加為0的最小n稱為域的特征，有限域必然有n存在特征為p的域中，對域中任意元素a必有pa=0GF(p)中，p為素數(shù)時，特征為p每個域的特征或為素數(shù)或為無窮第十一頁，共十九頁，編輯于2023年，星期五二元域GF(2)，模2運算GF(2)加減法一樣的結(jié)果GF(2)上有2n個n次多項式，xn的系數(shù)為1GF(2)上兩個多項式的運算滿足交換律、結(jié)合律和分配律GF(2)上任意的m次多項式能整除xn+1，其中n=2m-1m次不可約多項式若能整除xn+1，且n是滿足的最小正整數(shù)，n=2m-1，則這個m次不可約多項式成為“本原多項式”第十二頁，共十九頁，編輯于2023年，星期五GF(2m)以GF(p)上m次首一不可約多項式為模的多項式剩余類構(gòu)成pm階有限域GF(pm)GF(2)上次數(shù)小于等于m-1的多項式有2m個，構(gòu)成2m階有限域GF(2m)GF(2)是GF(2m)的基域，GF(2m)是GF(2)的擴域，二者的特征都是2GF(2m)={0,1,a,a2,a3,…,}第十三頁，共十九頁，編輯于2023年，星期五多項式GF(2)上的多項式f(X)，若是GF(2m)的一個元素，且是f(X)的根，則對任意l>0，是f(X)的根故有，易得

稱為x的共軛根，x的所有互異共軛根也是GF(2m)的元素(x是GF(2m)的元素)共軛根（元）具有相同的最小多項式，也就是說最小多項式包含所有互異的共軛元第十四頁，共十九頁，編輯于2023年，星期五最小多項式GF(q)中q-1個非零元素都是xq-1-1=0的根，反之xq-1-1=0的每個根都在GF(q)中，即任意元素的q-1次方都為1GF(2m)中2m-1個非零元素都是

的根，反之

的每個根都在GF(2m)中，即任意元素的2m-1次方都為1，也就是說GF(2m)中全體元素構(gòu)成了的全部根設是的一個根，其也可能是一個次數(shù)較低的多項式的根，設其中次數(shù)最低的多項式為，就是元素的最小多項式第十五頁，共十九頁，編輯于2023年，星期五最小多項式的最小多項式能整除任何一個GF(2)上的多項式，如果是的根最小多項式是不可約的GF(2m)的所有元素都的最小多項式都能整除任何一個GF(2)上的多項式，GF(2m)的元素是它的根，若不可約，則以本原元為根的最小多項式就是本原多項式第十六頁，共十九頁，編輯于2023年，星期五例子本原多項式為1+X+X4本原元a三種表示兩兩之間一一對應，三種形式等價第十七頁，共十九頁，編輯于2023年，星期五線性空間基底或基，一組線性無關(guān)的向量，其線性組合能表示線性空間V的所有向量零空間（即：解空間，對偶空間），V1是n維線性空間V的子空間，則與V1中每個向量正交的空間V中的其他向量構(gòu)成的子空間V2，V1和V2互為零空間假設有矩陣A