設計原理:如何在小尺寸DSP上實現2D條形碼解碼

　　條形碼一般被用於將關鍵的字母數字信息轉換為數字系統能夠掃描和讀取的符號信息，而無需每次都要將信息錄入數字系統。

　　1D（一維）條形碼只能對數字數據進行編碼，在過去二十年中主要用於產品運輸和追蹤、系統安全、超市等場合。使用 2D（二維）條形碼，數據在水平和垂直方向被編碼為 2D 符號，如下圖 1 所示。

　　2D 符號所能包含的數據量遠大於 1D 符號。2D 條形碼解決方案可比傳統 1D 條形碼提供更大的信息密度，特別是對於那些需要對精密信息而不是簡單的碼信息進行編碼的應用。

　　2D 條形碼技術的一些應用包括產品標籤、產品信息追蹤和檢驗、移動安全、出入境檢查服務、醫療保健和電子商務等。

　　圖 1：2D 條形碼示例

　　如今存在很多 2D 條形碼算法，這催生出採用不同條形碼技術的一系列應用。一般來說，有兩種類型的 2D 條形碼：1） 堆疊式 2D 條形碼，例如 PDF417 和 Code 49，2） 矩陣式條形碼，例如 QR 碼和數據矩陣。在這篇文章中，我們僅限於討論數據矩陣式條形碼技術［2］。

　　2D 數據矩陣式條形碼技術

　　2D 數據矩陣式條形碼包括在正方形或長方形中排列的黑色和白色模塊，如圖 1 所示。編碼數據位映射到黑色和白色模塊（或單元）組成的區域，稱為數據區域。關於 2D 數據矩陣式條形碼所支持的不同類型的編碼方案的詳細信息，請參見參考文獻［2］。

　　數據區域由定位圖形包圍（定位圖形的底部和左側只包含黑色模塊，而定位圖形的上部和右側由交替的白色和黑色模塊組成）。數據矩陣 2D 條形碼支持由排位圖形分隔的多個數據區域，從而能容納更多數據信息。

　　有兩種版本的數據矩陣，一種是基於循環冗餘校驗（CRC）和卷積糾錯，另一種是基於裡德所羅門（RS）糾錯。對於掃描、讀取和提取數據位，基於 CRC 與基於 RS 的數據矩陣解碼沒有區別。提取數據位之後，基於 CRC 的解碼與基於 RS 的解碼路徑不同，因為它們的交織和糾錯方法不同。

　

　　圖 2：2D 條形碼掃描器框圖和 DSP 處理內核

　　這裡我們考慮在小尺寸 Blackfin 處理器上對新興的基於 RS 碼的 2D 數據矩陣式條形碼進行解碼。通過 PPI-DMA 通道連接到 DSP 處理器的 2D 條形碼掃描器的框圖如上面圖 2 所示。

　　在小尺寸 DSP 上實現條形碼

　　傳感器對條形碼進行掃描並將像素數據通過並行埠接口（PPI）傳輸給 DSP。之後，DSP 處理器處理圖像像素並提取數據區域中黑色和白色模塊對應的數據位，然後進行糾錯。從掃描的 2D 條形碼的特定數據區域提取數據位的過程如下面圖 3 所示的流程圖。

　

　　圖 3：從 2D 數據矩陣符號提取數據位的流程圖

　　我們將 2D 數據矩陣式條形碼看做大小為 M x N 的圖像（通常是 QVGA 或 VGA 圖像）並進行處理。相機的 CMOS 傳感器捕獲圖像並將圖像像素傳輸給 DSP 進行處理。

　　現在的問題是，需要多大的存儲器來保存處理過程中的圖像？例如，以 VGA（即 640x480）為例，我們需要大約 300 kB 的數據存儲器來保存捕獲到的圖像。處理器內核的尺寸取決於其包含的存儲器的數量。

　　特別是 L1 高速存儲器，它佔用更多的矽面積，總成本也更高。因此，大多數處理器包含非常有限的 L1 存儲器。

另一方面，L2 或 L3 存儲器通常有較大的容量，佔用較小的面積，成本也較低。然而，它們速度較慢，需要通過 DMA 與處理器的工作存儲器（L1）進行數據傳輸。

　　接下來我們將討論用 Blackfin 系列的兩款不同處理器實現數據矩陣 2D 條形碼在，其中一款具有 16 kB 的 L1 和較大 L2/L3 存儲器，另一款只有 16 kB 的 L1 存儲器。

　　對於帶有 L2 和 L3 存儲器的處理器，捕獲的圖像通過 DMA 和 PPI 接口傳輸到 L2 存儲器。然後通過將少量圖像像素同時從 L2 移動到 L1 存儲器，來對 2D 條形碼中提取的數據位進行處理。在這種情況下，我們使用另一個 DMA 進行 L1 和 L2 之間的數據傳輸，整體解碼很簡單也不複雜。

　　在另一方面，如果僅有少量的 L1 存儲器，並且沒有 L2/L3 存儲器，那麼問題就相當棘手。在這種情況下，我們對同樣的條形碼要進行更多的掃描，並將目標區域（ROI）通過適當設置的 PPI-DMA 通道傳輸到 L1 存儲器進行處理。

　　雖然這個系統設置起來很複雜，但其成本和尺寸與前一個例子相比要小。接下來，我們將討論使用上面提到的兩個處理器實例對 2D 數據矩陣式條形碼進行解碼的技術。

　　用 L2 存儲器實施

　　在這種情況下，經掃描的所有圖像通過 PPI-DMA 通道被讀入 L2 存儲器，採用另一個存儲器 DMA 通過訪問 L2 中的部分圖像對其進行處理。如下圖 4（a）所示。

　　圖 4：用小尺寸 Blackfin 處理器進行 2D 條形碼解碼，

　　（a）具有 L2/L3 和 L1 存儲器，（b）僅有 L1 存儲器。

　　採用 OmniVision CMOS VGA 傳感器［3］，我們逐行獲得像素數據和控制信號、HREF（水平基準輸出）、VSYNC（垂直同步輸出）和 PCLK（像素時鐘輸出）。PPI-DMA 通道以 27 MHz 時鐘速率將像素讀入 L2 存儲器。在這種情況下，DMA 設置很簡單，因為我們在單次掃描中讀取整個圖像。

　　我們基本上遵循上面圖 3 所示的流程圖來從數據矩陣式條形碼模塊中提取數據位。如果在掃描的圖像中存在任何方向，我們能夠糾正方向和偏差，因為我們在 L2 存儲器中有全部圖像。

　　現在，我們假設圖像被正確掃描，沒有任何方向和偏差。首先，我們將數據矩陣式條形碼定位圖形的頂部幾行和右邊幾列從 L2 移入 L1 存儲器。在測量定位圖形中模塊的平均高度和寬度後，我們為定位圖形所有頂部和右邊模塊的中點做標記，將中點像素位置的 x 和 y 坐標值存入存儲器，留作以後使用。無 L2 或 L3 存儲器無 L2/L3 存儲器時，我們直接將圖像讀入 L1 存儲器。由於 L1 存儲器空間有限，我們一次

　　直接讀取整個圖像到 L1 存儲器中。如上圖 4（b）所示。

　　在這種情況下，進行條形碼解碼時我們要多次掃描圖像。使用 PPI 延遲和 PPI 計數寄存器，定位圖形模塊像素的頂部幾行和右邊幾列在一次掃描中被讀入 L1 存儲器。在這種情況下需要更多地 DMA 編程，因為我們需要從掃描器輸出將所選的圖像像素通過PPI-DMA 通道讀入 L1 存儲器。我們找到定位圖形模塊的大小及其中點位置坐標，並將其存儲起來為將來使用。

　　在圖像有細微方向或偏離時，我們讀取多行像素來糾正方向或偏差。這裡，我們逐行進行圖像處理，因為我們沒有完整的圖像。從數據矩陣式條形碼中提取數據位我們遵循下半部分流程圖（如之前圖 3 所示），從數據矩陣式條形碼黑色和白色模塊中提取位信息。

　　這裡，我們假設數據矩陣包含有黑色和白色模塊組成的單一數據區域。我們知道，有了定位圖形模塊的中點位置坐標，我們能很容易地獲得所有模塊中心點作為相交叉的水平線（與左側定位圖形垂直）。

　　它也通過定位圖形右側模塊的中點位置和垂直線（與定位圖形下邊垂直並通過定位圖形的上邊模塊的中點位置）。我們不能畫出所有這些線來標識交叉點，因為我們在 L1 存儲器中沒有完整的圖像。

　　然而，我們可以通過一次掃描一行的方式來獲得交叉點（使用定位圖形右側模塊中點的 y坐標作為行索引），將當前行列索引與定位圖形上邊模塊中點 x 坐標進行比較。

　　如果兩者相同，那麼就是交叉點，否則我們繼續掃描這一行。採用這一過程，我們掃描模塊的交叉點，並找到該位置像素的值。

　　如果像素值大於 128（即淺色），我們將該位解碼為 0，或者如果像素值小於 128，我們將該位解碼為 1。採用同樣的方式，我們能提取數據矩陣式條形碼數據區域的所有位。

　　對於具有 L2 存儲器的處理器，我們將與定位圖形右側模塊中點 y 坐標對應的像素行從 L2移入 L1 存儲器。當我們正在處理當前像素行時，使用 DMA 來移動下一像素行。但是，在使用無 L2 存儲器的處理器時，我們必須進行實時數據提取。此時，PPI-DMA 將下一行數據填入 L1 存儲器，我們必須完成對當前行的處理（進行基本的數據位提取）。

　　2D 解交織

　　據矩陣式條形碼使用 2D 交織的數據位。從數據區域模塊中提取數據位後，我們執行解交織來獲得糾錯碼字的數據位。關於 2D 數據位交織的詳細信息，請參見參考文獻［2］。

　　我們用預計算查找表來進行解交織。由於數據矩陣式條形碼支持不同尺寸的數據區域，因此解交錯查找表的大小和表單元也不同。不可能在小尺寸處理器中保存所有尺寸的查找表。然而，如果在預先給定的應用中數據矩陣大小是已知的，我們只需要存儲特定解交織查找表。解交織後，數據位按字節格式形成碼字，輸入 RS 解碼器。

　　條形碼糾錯

　　新興的 ECC-200 型數據矩陣式條形碼使用 RS （N， K）碼來糾正解交織位的錯誤和遺漏。RS （N， K）碼可以糾正最多（N-K）/2 個錯誤或者最多（N-K）個遺漏（如果不存在錯誤）。在這個應用中使用的 Galois 域是 GF（28）。對於不同數據區域大小，數據矩陣式條形碼使用不同的 RS 碼字長度。例如，14x14 大小的數據區域條形碼使用 RS（24， 12）碼來糾錯，16x16 大小的數據區域條形碼使用 RS（32， 18）碼。RS 解碼器的複雜度取決於數據區域的大小。隨著 RS 碼字長度的增加，存儲器需要存儲的所有 RS 解碼工作緩衝區也要增加。

　　為了高效地實施 RS 解碼器，我們使用查找表來進行 Galois 域計算。對所有 RS 碼字長度進行解碼時使用相同的 Galois 域對數和反對數查找表，因此域單元也屬於 GF（28）。我們需要大約 2 kB 的 L1 存儲器來存儲對數和反對數查找表。

　　數據矩陣式條形碼解碼複雜度

　　2D 條形碼解碼有兩個部分：1） 圖像處理，2）條形碼解碼。如果捕捉的圖像與解碼區域沒有適當對齊，我們可能需要進行圖像旋轉、偏差糾正等，來使圖像與解碼區域對齊。

　　在這種情況下，圖像處理階段的複雜度比實際條形碼解碼要大。在這篇文章中，我們假設圖像與解碼區域是對齊的。數據矩陣式條形碼的解碼複雜度（在周期和存儲器方面）取決於數據符號的大小。如果數據符號尺寸較大，每個符號中包含多個較大的數據區域，那麼我們需要更多的存儲器來保存圖像的行像素和 RS 工作緩衝。每單位時間需要處理的數據量也隨著數據區域的尺寸而增加。以每個數據矩陣式條形碼符號具有 16x16 數據區域的 VGA 圖像為例，我們需要大約 6kB數據存儲器和 4kB 的 Blackfin 程序存儲器。BF53x 內核上運行單個模塊的近似周期數如下：

　　模塊尺寸和數量：7，200

　　數據位提取： 2，000 個周期

　　解交織和封包：600

　　RS 解碼：7，000 個周期

　　本文小結

　　本文討論了在小尺寸 Blackfin 處理器上進行數據矩陣 2D 條形碼解碼。同時解釋了使用或不使用高延遲 L2 存儲器對 2D 條形碼進行解碼的不同方法。分析了基於 RS 的數據矩陣 2D條形碼解碼的複雜度，並估算了使用 BF53x 處理器對 VGA 圖像中單個 16x16 數據符號進行解碼所需的存儲器和周期數。