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

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

2、日，20點(diǎn)30分，星期二群的若干定理及性質(zhì)群中單位元唯一，每個(gè)元素的逆元唯一群中元素的個(gè)數(shù)稱為群的階循環(huán)群：群中每個(gè)元素都是a的某個(gè)整數(shù)次冪an，稱該群有a生成，a是該群的生成元使得an=1的最小正整數(shù)n，稱為a的級(jí)n階循環(huán)群中，任意元素的級(jí)是n的某個(gè)因子n階循環(huán)群中，每個(gè)n級(jí)的元素都稱為n次單位原根單位原根的個(gè)數(shù)是歐拉數(shù)第4頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二域非空集合F和F上定義的加法和乘法兩種運(yùn)算，滿足條件：F中全體元素構(gòu)成交換加群，有加法單位元0，a的逆元稱為負(fù)元，記為-aF中全體非零元素構(gòu)成交換乘群，乘法單位元為1加法和乘法之間滿足分配律記n個(gè)a相加為na，n個(gè)

3、a相乘為an，a0=1域中元素個(gè)數(shù)q稱為階，若元素個(gè)數(shù)有限，則稱為有限域或伽羅華域GF(q),Fq第5頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二子群，陪集若H是群G的非空子集，且依G上的運(yùn)算構(gòu)成群，則H是G的子群G有兩個(gè)平凡子群，自身和單位元構(gòu)成的群，其他非平凡子群稱為真子群對(duì)G的子群H，構(gòu)建g H=g h1, g h2, ，稱為左陪集，構(gòu)建 H g =h1 g, h2 g, ，稱為右陪集，陪集中最左邊的第一個(gè)稱為陪集首交換群中左陪集等于右陪集第6頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二陪集的性質(zhì)G關(guān)于H的所有陪集構(gòu)成G的一個(gè)劃分，即所有陪集的并就是G任意兩個(gè)

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

5、域的乘法結(jié)構(gòu)以素?cái)?shù)q為模的整數(shù)剩余類構(gòu)成q階有限域GF(q)；以GF(q)上m次首一不可約多項(xiàng)式為模的多項(xiàng)式剩余類構(gòu)成qm階有限域GF(qm)有限域GF(q)中非零元素構(gòu)成q-1階乘群(循環(huán)群)，其中存在一個(gè)生成元，級(jí)為q-1，是q-1次單位原根，稱為本原元GF(q)中q-1個(gè)非零元素都是xq-1-1=0的根，反之xq-1-1=0的每個(gè)根都在GF(q)中，即任意元素的q-1次方都為1第10頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二有限域的加法結(jié)構(gòu)滿足n個(gè)1（乘法單位元）相加為0的最小n稱為域的特征，有限域必然有n存在特征為p的域中，對(duì)域中任意元素a必有pa=0GF(p)中，p為

6、素?cái)?shù)時(shí)，特征為p每個(gè)域的特征或?yàn)樗財(cái)?shù)或?yàn)闊o(wú)窮第11頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二二元域GF(2)，模2運(yùn)算GF(2)加減法一樣的結(jié)果GF(2)上有2n個(gè)n次多項(xiàng)式，xn的系數(shù)為1GF(2)上兩個(gè)多項(xiàng)式的運(yùn)算滿足交換律、結(jié)合律和分配律GF(2)上任意的m次多項(xiàng)式能整除xn+1，其中n=2m-1m次不可約多項(xiàng)式若能整除xn+1，且n是滿足的最小正整數(shù)，n=2m-1，則這個(gè)m次不可約多項(xiàng)式成為“本原多項(xiàng)式”第12頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二GF(2m)以GF(p)上m次首一不可約多項(xiàng)式為模的多項(xiàng)式剩余類構(gòu)成pm階有限域GF(pm)GF(2)上

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

8、小多項(xiàng)式GF(q)中q-1個(gè)非零元素都是xq-1-1=0的根，反之xq-1-1=0的每個(gè)根都在GF(q)中，即任意元素的q-1次方都為1GF(2m)中2m-1個(gè)非零元素都是 的根，反之 的每個(gè)根都在GF(2m)中，即任意元素的2m-1次方都為1，也就是說GF(2m)中全體元素構(gòu)成了 的全部根設(shè) 是 的一個(gè)根，其也可能是一個(gè)次數(shù)較低的多項(xiàng)式的根，設(shè)其中次數(shù)最低的多項(xiàng)式為 ，就是元素 的最小多項(xiàng)式第15頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)30分，星期二最小多項(xiàng)式 的最小多項(xiàng)式 能整除任何一個(gè)GF(2)上的多項(xiàng)式 ，如果 是 的根最小多項(xiàng)式是不可約的GF(2m)的所有元素都的最小多項(xiàng)式都能整

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