2020年中國研究生數學建模競賽A題

2020年中國研究生數學建模競賽A題（華為公司命題）

ASIC芯片上的載波恢復DSP演算法設計與實作

光數字信號處理（DSP）芯片是光傳輸領域里的“心臟”，這種芯片往往是基于專用集成電路（ASIC）實作的，例如，采用7nm芯片工藝制造的光傳輸芯片容量可以達到800Gbps，相當于單光纖可實作48Tbps的容量，保障了網路流量的爆發型增長，ASIC芯片的DSP演算法設計通常包含兩個主要步驟，第一步是根據信道損傷的物理模型設計補償演算法，此時只需要考慮浮點計算；第二步是根據芯片資源和功耗約束，將演算法改造成ASIC芯片可實作的定點形式，此時需要將演算法細化為芯片上最基本的乘、加等運算，并考慮定點量化噪聲的影響，怎樣權衡性能和資源，實作具體場景下的最優設計，是DSP芯片演算法工程領域持久不變的課題，本題以oDSP中一種關鍵的載波恢復演算法為例，探討演算法與芯片的最優工程設計，

首先介紹關于基本通信系統和ASIC芯片上演算法設計的基本知識，

一、通信系統模型

本題考慮一個簡化的數字通信系統性能評估模型，如圖1所示，發送端編碼后的二進制序列映射調制為星座點上的符號并向外發送，每秒發送的符號個數稱為波特率fBaud，信號在信道中受到色散和相位噪聲的影響，并人為加入加性高斯白噪聲，噪聲量用信號和噪聲功率的比值表示，接收端先補償色散，再由載波恢復(Carrier Recovery, CR)演算法補償相位噪聲，最后信號進行判決后逆映射為二進制位元序列，受信道中損傷和噪聲影響，星座圖會發生[pq1] 擴散，從而導致信號判錯，使接收到的二進制序列與發端不一致，從而帶來誤碼，錯誤二進制位元占總二進制位元的比率稱為誤碼率（BER），只要BER小于某個門限，那么糾錯編碼后的BER就能夠小于1e-15次方量級，達到工程意義上的“無誤碼”傳輸，本題中不考慮糾錯編碼，BER均指直接判決后的BER，

演算法評估中常用RSNR（Required SNR）代價來評估演算法性能， SNR(Signal-to-Noise Ratio)指的是信號功率和噪聲功率的比例，例如圖1中，若只有加性高斯白噪聲存在時，對于給定的調制格式，SNR和BER存在關系也就確定了，將BER達到門限時信道中施加的SNR定義為Required SNR (RSNR)，它可理解為系統能夠容忍的噪聲量，當存在相位噪聲、色散等干擾后，相同糾前門限點對應的SNR值會提高，說明系統能夠容忍的噪聲量減少了，將RSNR的增加部分稱為RSNR代價，RSNR代價是衡量系統和演算法性能的常用指標，例如CR演算法性能越好，那么RSNR代價也應該越低，圖1 模型計算RSNR的噪聲是“人為”加入的，目的是用于評估系統性能，現實光傳輸系統中，噪聲可能有來自于電器件、光器件、光放大器等各種系統組件，

下面對模型中的術語做進一步解釋，

圖1 簡化數字通信系統性能評估模型

【調制、星座圖與誤碼率BER】

二進制序列通常需要將K個位元作為一個“符號”進行傳輸，每個符號有2K個不同狀態，光傳輸利用光波的復振幅承載信號，因此可用復平面上不同的點來對應不同的符號狀態，這種將符號狀態畫在復平面上的圖稱為“星座圖”，圖上的點稱為“星座點”，如圖2(a)所示的QPSK（Quadrature Phase Shift Keying）調制，經過信道疊加噪聲和接識訓處理后，接收端的星座圖不再是理想的四個點，而是會出現擴散，當接識訓收到1個符號時，就將發送的符號判定為離該符號最近的星座點，顯然，如果噪聲過大，接收到的符號可能被判錯從而產生誤碼，如圖2(b)中的藍點，誤碼率（Bit Error Ratio, BER）定義為錯誤的位元數占總傳輸位元數的比例，例如傳輸了50個符號共100個位元，其中有1個符號被誤判為相鄰的符號，錯誤了1個bit，則誤碼率為0.01，BER是衡量通信系統性能的最根本指標，

圖2 星座圖與噪聲導致誤碼的示意圖 圖3 信號和噪聲的相關定義示意圖

圖3中理想星座點用sk表示，接收到的符號用rk表示，則噪聲為

nk=rk-sk (1)

噪聲通常服從均值為0的正態分布，噪聲的方差等于噪聲的平均功率，定義為

Pn=1Nk=1Nnk2 (2)其中N為總共傳輸的符號數，信號平均功率定義為發送符號絕對值平方的均值：

Ps=1Nk=1Nsk2 (3)

定義信號和噪聲功率的比值為信噪比（Signal-to-Noise Ratio, SNR），

SNR=Ps/Pn (4)

工程上通常用dB作為SNR的單位，定義為

SNRdB=10log10(Ps/Pn) (5)

【相位噪聲與CR演算法】

相噪會對信號疊加一個時變的相位，

S1t=S0(t)exp?{jθt} (6)

其中S0(t)是疊加相噪前的波形，S1t是疊加相噪后的波形，θt是相噪，通信系統常用等間隔采樣后的離散方式表示，每個采樣點對應了某個時刻采樣到的波形，對于相位噪聲，k+1時刻和k時刻的相位差表示為：

dθ=θk+1-θk=2π*LWfb*Xk (7)

其中LW是一個激光器線寬指標，單位為kHZ，fb是波特率，而Xk是均值為0，方差為1的隨機變數，一個典型的相噪隨時間變化的規律如圖4所示，相位變化也有可能演化到負值，

圖4 典型相位噪聲演化曲線

如圖5所示，典型的CR演算法是間隔性地插入已知的導頻符號（Pilot），通過比較接收信號和已知符號的相位差，來估算出當前的相位噪聲，再將此相位差反乘到接收端受影響的符號上，就實作了相位噪聲的補償，Pilot占總符號的比例稱為Pilot開銷，例如每N個符號中包含M個Pilot，則開銷為M/N，在設計CR演算法時可以有各種考慮：例如應該盡可能減小Pilot以降低系統開銷，因為Pilot本身為已知量并不傳遞資訊；間插Pilot之間凈荷的相位可以通過各種插值方法來近似；加性白噪會影響相位估計精度，可以用2個連續的Pilot符號求平均以抑制白噪影響，也可以在間插的Pilot之間求平均，當然，以上僅是舉例，實際CR演算法不限于此，

圖5 Pilot的載波恢復演算法

【色散與色散補償演算法】

光纖中色散的效應，可認為是對信號直接做傅里葉變換后的頻域資料施加1個隨頻點平方關系變化的相位，如式8所示，

Hf=exp?[j*λ2πDzcf2] (8)

其中λ是波長，取1550nm，Dz是色散值，c是光速，f則是頻點，本題中，信道中施加色散和演算法中補償色散如圖6所示，假設色散值已知，則先FFT將接收到的資料轉換到頻域，再乘上式中的頻域回應，隨后再IFFT轉換回時域即可，信道中色散的頻域回應和演算法中補償色散的頻域回應呈共軛關系，

圖6 色散和色散補償方法

二、ASIC芯片上的演算法實作

與我們通常在計算機上開展的基于軟體的數學計算不同，在ASIC上的計算是基于硬體電路展開的，例如要計算某個公式，通用計算機上是轉換為一條條邏輯指令，按時間順序在相同的CPU中運行，最終輸出結果，而在ASIC上開展的計算，則是把計算程序拆分為具體的加法、乘法等基本操作，每一個基本操作都對應了不同的專用邏輯電路，在芯片上各自占據了一定的面積，設計ASIC芯片上的DSP演算法，需要考慮并行實作，定點量化，時序約束，和資源/功耗約束等約束，下面簡要敘述，

【并行實作】

芯片上的計算都是在系統時鐘下，以一拍一拍的節奏運行的，芯片計算的吞吐量必須要大于信號傳輸速度，才能確保資訊不丟失，如果采用串行的處理方式，芯片時鐘頻率極高，而芯片的功耗與時鐘主頻率近似呈平方關系，顯然不能通過一味提升主頻的方式增加處理流量，必須采用并行處理的方法，以資源換取處理流量的提升，例如圖7中所示的求平方操作，串行情況下1個時鐘周期處理1個符號，100G的波特率至少需要100GHz的時鐘主頻，遠遠超出了現實能達到的水平，若付出N倍的資源，每次同時計算N個符號，則時鐘主頻僅為1/N，功耗大大降低，當前oDSP時鐘主頻在500MHz~1GHz量級，對應符號的并行度約為100~200量級，

圖7 ASIC芯片并行運算示意圖

【定點量化】

計算機中常用雙精度浮點數來定義參變數，而ASIC通常用定點數來表示參變數的大小，雙精度浮點數在大多數計算情況下幾乎沒有精度損失，而ASIC定點數因為位數往往較小，舍入誤差增大，帶來量化噪聲，表示定點數的二進制位數稱為定點位寬，定點數常分為有符號和無符號位2種，如下圖所示，例如S(8,4)表示有符號的8-bit定點數，其中小數位占4位；u（7,4）代表無符號的7-bit定點數，其中小數位占4位，單個定點數僅能代表實數，復數則用2個定點分別代表實部和虛部，在ASIC中任何計算都應量化為定點數的計算，量化噪聲的影響也是演算法設計的關鍵之一，例如CR相噪演算法中，收端受影響的符號往往用6~9bit定點數表示，而計算相噪部分的位寬則根據實際情況而變化，

圖8 定點表示法

【基本操作、時序約束和資源/功耗約束】

ASIC上的演算法設計，需要將計算拆解為基本的操作，本題中考慮加法、乘法，查表和資料快取四類操作，其表示如圖9所示，加法和乘法均是對兩個數開展，復數運算拆分實部和虛部各自計算，減法可認為是先做一次乘以-1的乘法，再做一次加法，ASIC上由于是二進制定點數表示，乘以或除以2的冪次方相當于對小數點進行移位，不會帶來額外的資源代價，查表用于加法和乘法無法直接實作的操作，例如求sin函式，可以將輸入-輸出映射關系分別量化為離散輸入-輸出對應關系，通過查表的方式求得輸出，例如求 d=sin?(a+b2*c)， 首先一級加法計算a+b, 再通過移位得到a+b2，隨后一級乘法得到a+b2*c, 最后通過sin查表的方式得到d，每種運算都對應了芯片上的資源，顯然，參與運算的資料位寬越大，占用的資源也會更多，

圖9 ASIC芯片基本運算操作

另一方面，芯片是在時鐘主頻下一拍一拍運行，一拍運行中只能完成有限個連續的基本運算，但通過加快取的方式，可以實作流水的結構，例如圖10中，若運算1結果出來的時候，一拍內剩余的時間無法完成運算2，則需要在運算1的出口加入1級buff快取以存盤運算1的輸出資料，每拍運算時，運算2讀取buff中存盤的運算1的上一拍輸出開展計算，而運算1則和當前輸入資料開展運算，并將結果在存入buff中，這樣一來，每拍運行可以同時開展運算1和運算2，但會造成輸出的結果會比運算1和運算2在同一拍完成的情況延遲1拍，

圖10 快取實作流水結構

不同的運算路徑有著不同的時鐘延遲，當演算法存在不同的計算路徑時，需要保證每個路徑的延時對準，例如在CR演算法中，計算出的相位噪聲差需要反乘回資料，但相噪計算通常無法在1拍內完成，從而導致相位和資料有延時，需要用buffer將延時對準，本題中，假設1個時鐘周期最多完成1級乘法，4級加法，以及1級查表操作，

加法、乘法、查表和快取均需要占用資源，在演算法設計也應有所考慮，加法和乘法均是兩兩操作，加法資源近似與最大位寬呈正比，乘法資源近似與位寬乘積成正比，延時資源和位寬以及延時深度近似呈正比，對于一個M-N的查表，資源與(2^M)*N呈正比，M代表輸入位寬，N代表輸出位寬，例如：已知信號求相位的查表操作，信號位寬s(10,1)，相位位寬s(9,1)，此時的M=20，N=9，在查表時候的輸入為信號的【實部 虛部】組合，需要遍歷的地址有2^20，每個地址對應的相位值的位寬為s(9,1)，

表1

三、ASIC芯片演算法設計的典型步驟

綜合上述內容，芯片上演算法設計的通常包含以下具體步驟：

1) 根據物理模型和系數特性設計演算法原型：例如CR演算法中，采用Pilot估計相位差，并利用插值等方法計算出凈荷的相噪，最終將估計的相位差乘回資料以補償相噪，

2）在考慮并行度和時序約束的基礎上，將演算法細化為可實作的基本操作，并大致考慮演算法的實作復雜度對演算法實作的影響，此時可假設為浮點數，不需要考慮定點量化噪聲，例如CR演算法中，可能需要考慮凈荷相噪的插值如何由基本操作實作，計算噪聲路徑的延時如何與補償噪聲路徑的延時相匹配等，

3） 進一步考慮定點量化噪聲的影響，盡量以更低的資源實作，此時位寬優化是一個關鍵步驟，

----------------------------------------問題---------------------------------------------

問題1：考慮波特率為150Gbaud的標準16QAM信號，令線寬為100kHz，色散值為2萬ps/nm，演算法的并行度固定為128，不考慮定點量化，請以基本的加法、乘法、查表和快取為基礎，并以RSNR代價<0.3dB為目標，設計一套CR演算法，使得Pilot開銷最小？

問題2：考慮線寬從10kHz~10MHz，色散Dz從0~10,000 ps/nm變化場景，以RSNR代價<0.3dB為目標，定量挖掘色散、線寬與Pilot開銷的關系，

問題3：在問題2的場景上，進一步將芯片實作的資源納入考察，此時需考慮定點量化對性能和資源的影響，且導頻開銷可任意變化（但必須確保凈荷的流量為>145Gbaud），如何設計資源最低的CR演算法？

問題4：現實中性能和資源的權衡與具體場景有關，例如長距干線傳輸對性能要求往往比短距離要求更高，長距傳輸可付出更多的資源以降低RSNR代價，并選出問題3中你隊認為有代表性的1種場景，給出統籌性的“性能-資源”綜合考慮下的演算法設計思路，構造性能和資源的綜合代價函式，嘗試給出一套自動優化位寬和實作性設計的方案，并給出定量結果，用以指導演算法開發，

注：本題中均不考慮色散補償和誤碼率計算的復雜度和資源，只需考慮CR演算法（計算相噪+補償相噪）相關的資源即可，