許和乾，杜 煒

(合肥師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽 合肥 230601)

近年來，隨著科學(xué)技術(shù)的迅速發(fā)展，各種數(shù)據(jù)呈爆炸式增長，對于數(shù)據(jù)存儲的可靠性需求也不斷增強(qiáng)。2022年初，我國一體化大數(shù)據(jù)中心體系完成總體布局設(shè)計(jì)，“東數(shù)西算”工程正式全面啟動(dòng)。

高等代數(shù)作為數(shù)學(xué)專業(yè)本科階段最重要的基礎(chǔ)課之一，其教學(xué)內(nèi)容對培養(yǎng)學(xué)生的創(chuàng)新精神、創(chuàng)新觀念和創(chuàng)新能力起著不可替代的作用。研究基于一類特殊矩陣——范德蒙(Vandermonde)矩陣，探索如何通過研究性、探索性和開放性問題，以案例式、探究式或者是線上線下混合式等教學(xué)模式，培養(yǎng)學(xué)生的創(chuàng)新精神、創(chuàng)新觀念和創(chuàng)新能力。

1 RS糾刪碼

為了防止數(shù)據(jù)丟失，通常有兩種重要的方法：副本策略和編碼策略。前者將原始數(shù)據(jù)拷貝成多份放置在不同的設(shè)備中；后者則是將原始數(shù)據(jù)分塊并編碼生成冗余數(shù)據(jù)塊后存儲，可以保證丟失一定數(shù)量之內(nèi)的數(shù)據(jù)塊，原始數(shù)據(jù)仍然可以恢復(fù)。副本策略隨著數(shù)據(jù)量的增加，已經(jīng)變得存儲效率低下且費(fèi)用昂貴。因此，編碼策略越來越受到重視。

糾刪碼(Erasure Code)是編碼策略的一種，它是存儲領(lǐng)域常用的數(shù)據(jù)冗余技術(shù)，可以以更低的成本提供更高的可靠性，同時(shí)減小額外所需冗余設(shè)備的數(shù)量，從而提高存儲設(shè)備的利用率。糾刪碼在分布式存儲系統(tǒng)中的應(yīng)用通常包括陣列糾刪碼(Array Code: RAID5、RAID6等)、RS(Reed-Solomon)類糾刪碼和低密度奇偶校驗(yàn)糾刪碼(Low Density Parity Check Code，LDPC)。其中，陣列糾刪碼和RS類糾刪碼主要運(yùn)用于存儲和數(shù)字編碼領(lǐng)域；而LDPC碼目前則主要應(yīng)用于通信、視頻和音頻編碼等領(lǐng)域。

RS碼的基本原理如下：給定N個(gè)數(shù)據(jù)塊，根據(jù)這些數(shù)據(jù)塊生成M個(gè)校驗(yàn)塊；對于任意的N和M，從N個(gè)數(shù)據(jù)塊和M個(gè)校驗(yàn)塊中任取N塊都能恢復(fù)出原始的數(shù)據(jù)塊，即RS碼最多能容忍M個(gè)數(shù)據(jù)塊或者校驗(yàn)塊同時(shí)丟失。RS碼的編譯碼過程建立在有限域之上：假定有k個(gè)數(shù)據(jù)符號m0,m1,…,mk-1需要存儲，其中mi(0≤i≤k-1)均為有限域Fq中元素：通過構(gòu)造多項(xiàng)式P(x)=m0x+m1x2+…+mk-1xk-1，再求該多項(xiàng)式P(x)在A={α1,α1,…,αn}?Fq上n個(gè)不同點(diǎn)處的取值，便可得到RS碼的碼字：

c=(c0,c1,…,cn-1)=(P(α1),P(α2),…,P(αn))

(1)

其中數(shù)據(jù)符號的數(shù)量k被稱為該碼的維數(shù)，n稱為該碼的長度。一個(gè)RS(n,k)碼是指長度為n，維數(shù)為k的RS碼。事實(shí)上，通過利用RS碼對每k個(gè)數(shù)據(jù)符號進(jìn)行編碼，均能產(chǎn)生n-k個(gè)冗余，也就是校驗(yàn)符號。根據(jù)上述碼字的構(gòu)造方式，可得含有k個(gè)變量的線性方程組：

(2)

將其表示為矩陣形式，則有

(3)

式(3)左側(cè)矩陣通常被稱為RS碼的生成矩陣。可以看出，只需知道碼字c的任意不少于k個(gè)分量的值，上述方程組便存在唯一解，即可恢復(fù)k個(gè)數(shù)據(jù)符號。

RS碼作為一種經(jīng)典的MDS碼因?yàn)檫_(dá)到了Singleton界，在保護(hù)數(shù)據(jù)不丟失或者丟失部分?jǐn)?shù)據(jù)不影響整體功能的分布式存儲系統(tǒng)中有很大的用處[1]，并廣泛應(yīng)用于Google分布式文件系統(tǒng)GFS、微軟Azure云存儲系統(tǒng)和Facebook HDFS中[2-4]。

2 范德蒙行列式的實(shí)踐教學(xué)探索

2.1 課堂教學(xué)中的范德蒙行列式

范德蒙行列式在現(xiàn)行高等代數(shù)教材中，通常只是一道例題：

例1[5]：行列式

(4)

稱為n階的范德蒙行列式?？梢宰C明，對任意的n(n≥2)，n階范德蒙行列式等于a1,a2,…,an這n個(gè)數(shù)所有可能的差ai-aj(1≤j≤i≤n)的乘積。如果授課教師按照一般教學(xué)邏輯，只利用數(shù)學(xué)歸納法簡單介紹其證明過程，就會(huì)導(dǎo)致學(xué)生難以理解該行列式的具體含義，無法做到學(xué)以致用，無法達(dá)到在課堂教學(xué)中培養(yǎng)學(xué)生創(chuàng)新精神這一根本目標(biāo)。

2.2 基于范德蒙行列式，引入范德蒙矩陣

范德蒙矩陣是法國數(shù)學(xué)家范德蒙提出的一種各列為幾何級數(shù)的矩陣。通常假定a1,a2,…,an為數(shù)域Fq中兩兩互異的數(shù)且不為0，則形如：

(5)

的m×n矩陣或其轉(zhuǎn)置均稱為范德蒙矩陣。教師可以在教學(xué)中通過范德蒙行列式，引入范德蒙矩陣。事實(shí)上，RS碼的生成矩陣就是一個(gè)范德蒙矩陣。

可以看出，范德蒙矩陣的任一k階子矩陣均可逆。當(dāng)m=n時(shí)，就會(huì)得到一個(gè)n階范德蒙方陣，其行列式即為例1中的范德蒙行列式。根據(jù)例1，對任意的n(n≥2)，n階范德蒙行列式d=∏1≤j≤i≤n(ai-aj)。

2.3 范德蒙矩陣在RS糾刪碼中的應(yīng)用

教師可以通過探索范德蒙矩陣在實(shí)際中的應(yīng)用，讓學(xué)生真切地感受到所學(xué)習(xí)的數(shù)學(xué)概念、數(shù)學(xué)知識都是來源于實(shí)踐并扎根于實(shí)踐中的，而不是所謂的“空中樓閣”。例如，Google GFS II(Colossus)中，便采用了最基本的RS(6，3)編碼。將一個(gè)待編碼的數(shù)據(jù)單元分為6個(gè)數(shù)據(jù)子塊， 然后添加3個(gè)校驗(yàn)子塊，最多可容忍包括校驗(yàn)子塊在內(nèi)的任意3個(gè)子塊錯(cuò)誤，其基本結(jié)構(gòu)如圖1所示。

圖1 糾刪碼結(jié)構(gòu)示意圖

利用一個(gè)“生成矩陣”G乘數(shù)據(jù)塊D，從而建立數(shù)據(jù)塊D和校驗(yàn)塊P之間的聯(lián)系；由于矩陣運(yùn)算的可逆性，系統(tǒng)也就具備了容忍若干個(gè)數(shù)據(jù)塊失效的能力。以下將利用矩陣的語言簡單闡述RS(6，3)編碼的基本原理。

(6)

由矩陣(6)可以看出，編碼后的信息塊C產(chǎn)生了冗余，前6行還是原始數(shù)據(jù)，即數(shù)據(jù)塊D，后3行為冗余數(shù)據(jù)，即校驗(yàn)塊P。如果信息塊C在存儲過程中，有不超過3個(gè)子塊失效，以子塊D1、P2和P3失效為例，可將GD=C中對應(yīng)的第1、8、9行刪除得到：

(7)

(8)

即數(shù)據(jù)塊得到了恢復(fù)。

由于RS編碼中的G′使用了范德蒙矩陣，其特性決定了生成矩陣G中的G′在保證G刪除任意的3行后得到的矩陣一定可逆。通過以上的例子可以發(fā)現(xiàn)，范德蒙矩陣在實(shí)踐當(dāng)中有著非常重要的應(yīng)用。

3 結(jié)語

當(dāng)授課教師在介紹一個(gè)數(shù)學(xué)概念時(shí)，有時(shí)需要說明概念的背景和用途；講解一個(gè)定理時(shí)，有時(shí)要重點(diǎn)介紹證明的思路；而計(jì)算一個(gè)例子時(shí)，有時(shí)可以進(jìn)一步探索它在實(shí)踐中的應(yīng)用。教師要認(rèn)真梳理已有的知識點(diǎn)，找到其間的聯(lián)系，并能夠善于將一些重要的知識點(diǎn)進(jìn)行拓展和串聯(lián)，將基本的數(shù)學(xué)思想和方法傳授給學(xué)生。同時(shí)，教師可以適當(dāng)?shù)卦诮虒W(xué)中介紹所講授的知識在科研中的應(yīng)用，分析科研思路，培養(yǎng)學(xué)生在學(xué)會(huì)做科研的同時(shí)，善于發(fā)現(xiàn)問題和提出問題。通過對前沿科研知識的介紹，可以嘗試讓學(xué)生探索一些具有研究性、探索性和開放性的問題，以案例教學(xué)、探究式教學(xué)或者是線上線下混合式等教學(xué)模式進(jìn)一步展開教學(xué)活動(dòng)。通過不斷的訓(xùn)練，充分激發(fā)學(xué)生學(xué)習(xí)興趣，更好地培養(yǎng)學(xué)生的創(chuàng)新精神、創(chuàng)新觀念和創(chuàng)新能力。