編碼技術(shù)數(shù)學(xué)基礎(chǔ)

1、編碼技術(shù)數(shù)學(xué)基礎(chǔ)第1頁，共19頁，2022年，5月20日，20點30分，星期二簡單基礎(chǔ)最大公約數(shù)GCD最小公倍數(shù)LCM同余和剩余類同余類的加減乘除第2頁，共19頁，2022年，5月20日，20點30分，星期二群一個系統(tǒng)、一種數(shù)學(xué)系統(tǒng)、一種代數(shù)結(jié)構(gòu)非空集合G和G上定義的一種運算“”，并滿足條件：封閉性，任意兩個集合中元素的運算結(jié)果仍是集合的元素, 即任意a,bG，有a b G結(jié)合律，(ab)c=a(bc)存在單位元e對任意集合中元素a，有逆元a-1，使得a a-1=a-1a=e規(guī)定：n個a的運算記為a a a=an，a0=e滿足交換律的群叫交換群或Abel群第3頁，共19頁，2022年，5月20

2、日，20點30分，星期二群的若干定理及性質(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ù)第4頁，共19頁，2022年，5月20日，20點30分，星期二域非空集合F和F上定義的加法和乘法兩種運算，滿足條件：F中全體元素構(gòu)成交換加群，有加法單位元0，a的逆元稱為負元，記為-aF中全體非零元素構(gòu)成交換乘群，乘法單位元為1加法和乘法之間滿足分配律記n個a相加為na，n個

3、a相乘為an，a0=1域中元素個數(shù)q稱為階，若元素個數(shù)有限，則稱為有限域或伽羅華域GF(q),Fq第5頁，共19頁，2022年，5月20日，20點30分，星期二子群，陪集若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, ，稱為右陪集，陪集中最左邊的第一個稱為陪集首交換群中左陪集等于右陪集第6頁，共19頁，2022年，5月20日，20點30分，星期二陪集的性質(zhì)G關(guān)于H的所有陪集構(gòu)成G的一個劃分，即所有陪集的并就是G任意兩個

4、陪集的任意元素都不同陪集的大小是H的階，所有陪集大小相同第7頁，共19頁，2022年，5月20日，20點30分，星期二有限域上的多項式系數(shù)取自Fq上的x的多項式稱為有限域上的多項式，全體這類多項式的集合記為GF(q)x或Fqx全體系數(shù)都為0的零多項式，記為0，x的最高次項為1的多項式稱為首一多項式不可約多項式：除了常數(shù)和本身，沒有其他非零次多項式為因子第8頁，共19頁，2022年，5月20日，20點30分，星期二多項式的概念次數(shù)、根多項式的歐幾里得除法多項式互素多項式的最大公因式GCD多項式的最小公倍式LCM多項式的同余和剩余類第9頁，共19頁，2022年，5月20日，20點30分，星期二有限

5、域的乘法結(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第10頁，共19頁，2022年，5月20日，20點30分，星期二有限域的加法結(jié)構(gòu)滿足n個1（乘法單位元）相加為0的最小n稱為域的特征，有限域必然有n存在特征為p的域中，對域中任意元素a必有pa=0GF(p)中，p為

6、素數(shù)時，特征為p每個域的特征或為素數(shù)或為無窮第11頁，共19頁，2022年，5月20日，20點30分，星期二二元域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次不可約多項式成為“本原多項式”第12頁，共19頁，2022年，5月20日，20點30分，星期二GF(2m)以GF(p)上m次首一不可約多項式為模的多項式剩余類構(gòu)成pm階有限域GF(pm)GF(2)上

7、次數(shù)小于等于m-1的多項式有2m個，構(gòu)成2m階有限域GF(2m)GF(2)是GF(2m)的基域， GF(2m)是GF(2)的擴域，二者的特征都是2GF(2m)=0,1,a,a2,a3, 第13頁，共19頁，2022年，5月20日，20點30分，星期二多項式GF(2)上的多項式f(X)，若 是GF(2m)的一個元素，且是f(X)的根，則對任意l0， 是f(X)的根 故有 ，易得 稱為x的共軛根，x的所有互異共軛根也是GF(2m)的元素(x是GF(2m)的元素)共軛根（元）具有相同的最小多項式，也就是說最小多項式包含所有互異的共軛元第14頁，共19頁，2022年，5月20日，20點30分，星期二最

8、小多項式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ù)較低的多項式的根，設(shè)其中次數(shù)最低的多項式為 ，就是元素 的最小多項式第15頁，共19頁，2022年，5月20日，20點30分，星期二最小多項式 的最小多項式 能整除任何一個GF(2)上的多項式 ，如果 是 的根最小多項式是不可約的GF(2m)的所有元素都的最小多項式都能整

9、除任何一個GF(2)上的多項式 ， GF(2m)的元素 是它的根，若 不可約，則以本原元為根的最小多項式就是本原多項式第16頁，共19頁，2022年，5月20日，20點30分，星期二例子本原多項式為1+X+X4本原元a三種表示兩兩之間一一對應(yīng)，三種形式等價第17頁，共19頁，2022年，5月20日，20點30分，星期二線性空間基底或基，一組線性無關(guān)的向量，其線性組合能表示線性空間V的所有向量零空間（即：解空間，對偶空間），V1是n維線性空間V的子空間，則與V1中每個向量正交的空間V中的其他向量構(gòu)成的子空間V2， V1和V2互為零空間假設(shè)有矩陣Amxn行空間，由矩陣的m行張成的空間，是n維向量空間V的