快速響應矩陣碼（下）

書接上回，繼續下半場。

糾錯碼

QR 碼採用糾錯演算法生成一系列糾錯碼字，添加在數據碼字序列之後，使得符號可以在遇到損壞時可以恢復。這就是為什麼二維碼即使有殘缺也可以掃出來。沒有殘缺創造殘缺也要把它掃出來，相信大家見過很多中間帶圖標的二維碼吧。

糾錯碼字可以糾正兩種類型的錯誤，拒讀錯誤（錯誤碼字的位置已知）和替代錯誤（錯誤碼字位置未知）。一個拒讀錯誤是一個沒掃描到或無法解碼的符號字元，一個替代錯誤是錯誤解碼的符號字元。如果一個缺陷使深色模塊變成淺色模塊，或將淺色模塊變成深色模塊，將符號字元錯誤地解碼為是另一個不同的碼字，造成替代錯誤，這種數據替代錯誤需要兩個糾錯碼字來糾正。

糾錯等級

糾錯共有 4 個等級，對應 4 種糾錯容量，如下表所示。

用戶應確定合適的糾錯等級來滿足應用需求。從 L 到 H 四個不同等級所提供的檢測和糾錯的容量逐漸增加，其代價是對錶示給定長度數據的符號的尺寸逐漸增加。例如，一個版本為 20-Q 的符號能包含 485 個數據碼字，如果可以接受一個較低的糾錯等級，則同樣的數據也可用版本 15-L 的符號表示（準確數據容量為 523 個碼字）。

糾錯等級的選擇與下列因素相關：

1. 預計的符號質量水平：預計的符號質量等級越低，應用的糾錯等級就應越高。
2. 首讀率的重要性。
3. 在掃描誤讀失敗後，再次掃描的機會。
4. 印刷符號的空間限制了使用較高的糾錯等級。

糾錯等級【L】適用於具有高質量的符號以及/或者要求使表示給定數據的符號儘可能最小的情況。等級【M】被認為是“標準”等級，它具有較小尺寸和較高的可靠性。等級【Q】是具有“高可靠性”的等級，適用於一些重要的或符號印刷質量差的場合，等級【H】提供可實現的最高的可靠性。

糾錯碼字的生成

QR 碼的糾錯使用 Reed–Solomon 編碼，有關 Reed–Solomon 碼，可以參考這篇文章：http://article.iotxfd.cn/RFID/Reed%20Solomon%20Codes。這裡我只大概介紹一下計算過程。

糾錯碼字的生成多項式

糾錯碼字是用數據碼字除糾錯碼多項式所得到的餘數。糾錯碼多項式我們可以查表得出，首先查下表 3：QR碼符號各版本的糾錯特性。這裡我僅列出小部分，完整表數據請查看 GB/T 18284-2000 中的表 9。

其中（c，k，r)：c=碼字總數；k=數據碼字數；r=糾錯容量。

之前【例 1 續 1】確定使用的是版本1-H，查表得到糾錯碼字數為：17（上表紅框部分）。碼字總數為 26 表示此版本 QR 碼可容納的總數據量，其中數據碼字占 9 個，糾錯碼字占 17 個。接下來根據糾錯碼字數 17 來查找多項式。可在 GB/T 18284-2000 附錄 A 的糾錯碼字的生成多項式表中查找，也可使用生成多項式工具創建它，下表 4 只列出小部分內容：

Reed–Solomon 碼的 C# 實現

大家可能會問了，之前生成的糾錯碼字怎麼跟這個多項式除啊？直接除肯定是不行的，首先要把查到的多項式轉化為對應的一組數字。上表查到 17 所對應的生成多項式可轉化為：[1, 119, 66, 83, 120, 119, 22, 197, 83, 249, 41, 143, 134, 85, 53, 125, 99, 79]。用數據碼字除這組數字所得餘數，就是我們的糾錯碼字了。當然，這個過程是使用程式來完成的。Reed–Solomon 編碼這篇文章詳細講述瞭如何使用 Python 實現這個功能。我將需要用到的代碼翻譯成了 C#：

using System;

namespace QRHelper
{
    class ECC
    {
        const int PRIM = 0x11d;

        private static byte[] gfExp = new byte[512]; //逆對數(指數)表
        private static byte[] gfLog = new byte[256]; //對數表

        static ECC()
        {
            byte x = 1;
            for (int i = 0; i <= 255; i++)
            {
                gfExp[i] = x;
                gfLog[x] = (byte)i;
                x = Gf_MultNoLUT(x, 2);
            }

            for (int i = 255; i < 512; i++)
            {
                gfExp[i] = gfExp[i - 255];
            }
        }

        //伽羅華域乘法
        private static byte Gf_MultNoLUT(int x, int y)
        {
            int r = 0;
            while (y != 0)
            {
                if ((y & 1) != 0)
                {
                    r ^= x;
                }
                y >>= 1;
                x <<= 1;
                if ((x & 256) != 0)
                {
                    x ^= PRIM;
                }
            }
            return (byte)r;
        }

        //伽羅華域乘法
        private static byte GfMul(byte x, byte y)
        {
            if (x == 0 || y == 0)
            {
                return 0;
            }
            return gfExp[gfLog[x] + gfLog[y]];
        }

        //伽羅華域冪
        private static byte GfPow(byte x, int power)
        {
            return gfExp[(gfLog[x] * power) % 255];
        }

        //多項式 乘法
        private static byte[] GfPolyMul(byte[] p, byte[] q)
        {
            byte[] r = new byte[p.Length + q.Length - 1];
            for (int j = 0; j < q.Length; j++)
            {
                for (int i = 0; i < p.Length; i++)
                {
                    r[i + j] ^= GfMul(p[i], q[j]);
                }
            }
            return r;
        }

        /// <summary>
        /// 獲取糾錯碼字的生成多項式
        /// </summary>
        /// <param name="nsym">糾錯碼字數</param>
        /// <returns>由一組數字表示的生成多項式</returns>
        public static byte[] RsGeneratorPoly(int nsym)
        {
            byte[] g = { 1 };
            for (int i = 0; i < nsym; i++)
            {
                g = GfPolyMul(g, new byte[] { 1, GfPow(2, i) });
            }
            return g;
        }

        /// <summary>
        /// 生成糾錯碼，並添加在數據碼字之後
        /// </summary>
        /// <param name="msgIn">數據碼字</param>
        /// <param name="nsym">糾錯碼字數</param>
        /// <returns>數據碼字+糾錯碼字</returns>
        public static byte[] RsEncodeMsg(byte[] msgIn, int nsym)
        {
            if (msgIn.Length + nsym > 255)
            {
                throw new ArgumentException("數組長度超過 255！");
            }
            //byte[] gen = generators[(byte)nsym];
            byte[] gen = RsGeneratorPoly(nsym);
            byte[] msgOut = new byte[msgIn.Length + gen.Length - 1];
            Array.Copy(msgIn, 0, msgOut, 0, msgIn.Length);

            for (int i = 0; i < msgIn.Length; i++)
            {
                byte coef = msgOut[i];
                if (coef != 0)
                {
                    for (int j = 1; j < gen.Length; j++)
                    {
                        msgOut[i + j] ^= GfMul(gen[j], coef);
                    }
                }
            }
            Array.Copy(msgIn, 0, msgOut, 0, msgIn.Length);

            return msgOut;
        }
    }
}

代碼量是相當少啊！根據不用上網找演算法包。在實際開發中，如果需要繪製大量 QR 碼，完全可以將所有 31 個生成多項式轉化結果存放在集合中，使用時直接查詢即可得出，這樣可以大大加快生成速度。上述代碼中的RsGeneratorPoly()方法用於生成多項式，它會產生大量臨時數組。有了代碼，可以繼續我們之前的例子了。

【例 1 續 2】：生成完整碼字

之前在【例 1 續 1】中，我們已經生成了數據碼字：
00010000,00100000,00001100,01010110,01100001,10000000,11101100,00010001,11101100

16 進位表示形式為：0x10, 0x20, 0x0C, 0x56, 0x61, 0x80, 0xEC, 0x11, 0xEC

接下來使用如下代碼生成完整碼字：

byte[] msgin = { 0x10, 0x20, 0x0C, 0x56, 0x61, 0x80, 0xEC, 0x11, 0xEC };
byte[] msg = ECC.RsEncodeMsg(msgin, 17);

得到結果：0x10 0x20 0x0C 0x56 0x61 0x80 0xEC 0x11 0xEC 0x0E 0x9D 0x02 0xC8 0xC2 0x94 0xF3 0xA7 0xAD 0x8D 0xE2 0x0A 0xF4 0xA5 0x2B 0xAC 0xDF

以上就是我們要填入 QR 碼圖案的所有 26 個碼字了。前 9 個為數據碼字，後 17 個為糾錯碼字，程式已經幫我們自動連接好了。

構造信息的最終碼字序列

上例中，糾錯的塊數只有 1 塊，只需簡單將數據碼字連接糾錯碼字連接，組成 1 塊數據即可。而在絕大多數版本中，存在多個糾錯碼塊數。下麵講解多塊糾錯碼塊折構造。

以版本 5-H 舉例，查表 3 的版本 5 部分，如下所示：

版本 5-H 碼字共分為 4 塊，其中 2 塊碼字總數為 33 個，包括 11 個數據碼字和 22 個糾錯碼字；另 2 塊碼字總數為 34 個，包括 12 個數據碼字和 22 個糾錯碼字。首先取出數據碼字的前 11 個數據碼字，計算 22 個糾錯碼字，連接形成塊 1 數據；再從數據碼字中取 11 個碼字生成塊 2 數據；繼續從數據碼字中取 12 個碼字生成塊 3 數據；將最後 12 個數據碼字取出並生成塊 4 數據。

各塊字元的按下表進行佈置，表中的每一行對應一個塊的數據碼字（表示為Dn）和相應塊的糾錯碼字（表示為En）；

版本 5-H 符號的最終碼字序列為：
D1,D12,D23,D35,D2,D13,D24,D36,...D11,D22,D33,D45,D34,D46,E1,E23,E45,E67,E2,E24,E46,E68,...E22,E44,E66,E88。在某些版本中，需要 3、4 或 7 個剩餘位方能填滿編碼區域模塊數，此時需在最後的碼字後面加上剩餘位（0）。

格式信息

格式信息用於存放糾錯等級和掩模信息，是一個 15 數據，由 2位糾錯指示符 + 3位掩模圖形參考 + 10位糾錯碼組成。

格式信息的計算

首先糾錯指示符由 2 個位表示，各糾錯等級所對應的數字見下表5。

掩模圖形參考使用 3 個位表示，由數字 0~7 表示，將其轉換為 3 位二進位即可，掩模將在稍後介紹，現在你只需要知道占用 3 個位就行了。

將 2位糾錯指示符 + 3位掩模圖形參考，得到 5 位數據碼，並使用 BCH(15,5) 編碼計算得到糾錯碼。

BCH 碼

BCH 碼和 Reed–Solomon 碼類似，可以參考 Reed–Solomon 編碼這篇文章。Reed–Solomon 碼使用多項式除法得出糾錯碼序列，而 BCH 碼就簡單得多，它按位運算得出糾錯碼。BCH(15,5) 表示 BCH 碼總長度為 15 位，其中數據碼為 5 位，糾錯碼 10 位。Reed–Solomon 碼有生成多項式，BCH 碼使用的是生成碼：10100110111。使用數據碼除以生成碼，所得餘數就是糾錯碼。由於 BCH 碼的運算很簡單，下麵演示數據碼 00101 的演算過程。

1. 將數據碼左移 10 位，湊夠 15 位，得到二進位數字：001010000000000
2. 將上面數字除以 10100110111（0x537），使用長除法，如下圖所示：

上圖中的餘數取 10 位即為糾錯碼：0011011100

1. 將 5 位數據碼 00101 與糾錯碼相連，即得到最終格式信息碼：001010011011100（0x14DC）

使用程式實現非常簡單，在ECC類中添加如下代碼：

 //生成 BCH 碼
private static int CheckFormat(int fmt)
{
    int g = 0x537;
    for (int i = 4; i >= 0; i--)
    {
        if ((fmt & (1 << (i + 10))) != 0)
        {
            fmt ^= g << i;
        }
    }
    return fmt;
}

/// <summary>
/// 生成 BCH(15,5) 糾錯碼，並返回完整格式信息碼
/// </summary>
/// <param name="data">數據碼</param>
/// <returns>返回完整格式信息碼</returns>
public static int BCH_15_To_5_Encode(int data)
{
    data <<= 10;
    return data ^ CheckFormat(data);
}

使用以下代碼生成完整格式信息碼：

int code = ECC.BCH_15_To_5_Encode(5);

結果為：5340（0x14DC）

格式信息的掩模

為確保糾錯等級和掩模圖形參考（稍後介紹）合在一起的結果不全是 0，需將 15 位格式信息與掩模圖形 101010000010010（0x5412）進行異或運算。

格式信息的繪製

QR 碼中有專門的區域繪製格式信息，見下圖：

由於格式信息的正確解碼對整個符號的譯至關重要，它會在 QR 碼中繪製兩次以提供冗餘。格式信息的最低位模塊編號為 0，最高位編號為 14。為避免混淆，下表標示了之前生成格式信息與掩模圖形以及兩者進行 XOR 運算之後的結果的各個位編號。

左上角繪製區域編號 8、9 之間和 5、6 之間的深色模塊被定點陣圖形使用，不用於繪製格式信息。左下角編號 8 上的 Dark Module 永遠為深色模塊，不用於存放任何信息。

接下來我們將 XOR 後的結果繪製到 QR 碼中的格式信息區域，如下圖所示：

圖中綠色區域為格式信息區域，其中淺綠色表示淺色模塊，深綠色表示深色模塊。

【例 1 續 3】：生成格式信息

接下來我繼續【例 1】，添加格式信息：

1. 之前【例 1】中我們選擇了糾錯等級為 H，查表 5，得到數字：10
2. 假設我們選擇的掩模圖形參考為 011，則最終數據碼為：10011
3. 使用之前的程式將 10011 生成完整格式信息碼：100110111000010（0x4DC2）
4. 將生成的格式信息碼與 101010000010010（0x5412）進行異或運算，結果為：
   001100111010000（0x19D0）
5. 將結果繪製到格式信息區域中，最終結果如下圖所示：

版本信息

版本信息用於存放 QR 碼的版本號。其中，6 位數據位，12 位通過 BCH(18,6) 編碼計算出的糾錯位。只有版本 7~40 的符號包含版本信息。版本 0~6 無需繪製版本號。

版本信息的計算

版本信息的計算和格式信息類似，也是使用長除法。只是這一次使用的生成碼為：1111100100101（0x1F25）。以下為 BCH(18,6) 的 C# 代碼：

public static int BCH_18_6_Encode(int data)
{
    int g = 0x1F25;
    int fmt = data << 12;
    for (int i = 5; i >= 0; i--)
    {
        if ((fmt & (1 << (i + 12))) != 0)
        {
            fmt ^= g << i;
        }
    }
    return (data << 12) ^ fmt;
}

下麵以版本號 7 為例，計算版本信息碼：

1. 版本號 7 轉換為 6 位二進位數據碼：000111
2. 將以上數據碼左移 12 位，湊夠 18 位：000111000000000000
3. 將上面數字除以生成碼 1111100100101（0x1F25），得到餘數：110010010100
4. 將數據碼與得到的餘數相連，得到最終版本信息碼：000111110010010100

與格式信息不同，版本信息碼生成後不再需要單獨進行掩模運算。

版本信息的繪製

由於版本信息的正確解碼是整個符號正確解碼的關鍵，因此版本信息在符號中出現兩次以提供冗餘。第一個存放位置在定點陣圖形上面，由6行×3列模塊組成，其右緊臨右上角位置探測圖形的分隔符；第二個存放位置在定點陣圖形左側，其下邊緊臨左下角位置探測圖形的分隔符，如下圖的藍色部分所示：

格式信息的最低位模塊編號為 0，最高位編號為 17。接下來我們將之前計算的版本 7 的版本信息碼繪製到 QR 碼中的版本信息區域。效果如下圖所示，紅色部分為版本信息，其中，深紅色代表深色模塊，粉紅色代表淺色模塊。：

至此，所有功能圖形以及格式圖形都已經繪製完畢，並已全部顯示在這上圖中。接下來，終於可以開始繪製數據碼字了。

符號字元的佈置

在 QR 碼符號的編碼區域中，符號字元以 2 個模塊寬的縱列從符號右下角開始佈置，並自右向左，且交替地從下向上或從上向下安排。GB/T 18284-2000 用了很長一段篇幅講解編碼佈置規則，其實很簡單，就是以兩列為單位向上或向下佈置，列內蛇形走位，遇障礙跳過。為方便大家學習，我在《QR助手程式》中加入了繪製走位路線的功能，下圖是版本1和版本7的走位路線：

這飄忽不定的神仙步伐，銷魂啊！從右下角開始，延著一條不中斷的線一直到左下角結束，將最終數據碼流從左到右，按這條線的方向佈置在沿途遇到的粉紅色模塊中，即完成符號字元的佈置。相信大家一眼就能看懂。我之所以要實現這個走位路線的繪製功能，一方面是手繪這兩張圖太痛苦了，另一方面也是為了方便驗證走位演算法是否存在錯誤。

【例 1 續 4】：佈置符號字元

【例 1 續 2】中我們生成了最終的數據碼字為：
0x10 0x20 0x0C 0x56 0x61 0x80 0xEC 0x11 0xEC 0x0E 0x9D 0x02 0xC8 0xC2 0x94 0xF3 0xA7 0xAD 0x8D 0xE2 0x0A 0xF4 0xA5 0x2B 0xAC 0xDF

現在終於可以將其依照之前的路線填入編碼區域中了。效果如下圖所示：

圖中粉紅色模塊就是我們剛纔填入的數據。終於可以慶祝一下了，放鬆一下可以，但不能端酒！事情還沒完！

掩模

QR 碼中如果出現大面積的空白或黑塊，會導致掃描器識別困難。為了讓 QR 圖形看起來儘可能凌亂，且儘可能避免位置探測圖形中的點陣圖 1011101 的出現，需對 QR 圖形進行掩模操作，步驟如下：

1. 掩模不用於功能圖形及格式圖形：尋像圖形、定點陣圖形、校正圖形、位置探測圖形分隔符、格式信息和版本信息。
2. 數據碼字與掩模圖形進行 XOR 操作後再進行繪製。
3. 對每個結果圖形的不合要求的部分記分，以評估這些結果。
4. 選擇得分最低的圖形。

掩模圖形

下表給出了掩模圖形的參考和掩模圖形生成的條件。掩模圖形是通過將編碼區域（不包括格式信息和版本信息）內那些條件為真的模塊定義為深色而產生的。所示的條件中，i 代表模塊的行的位置，j 代表模塊的列的位置，（i,j)=(0,0)代表符號中左上角的位置。

下圖顯示了所有掩模圖形的外觀：

下麵是掩模後的效果，我們可以看到整塊的數據掩模後變得比較零散了。

【例 1 續 5】：加入掩模圖形

最後，我們將【例 1 續 4】得到的圖案中的粉紅色模塊同掩模圖案進行 XOR 運算。將所有深色圖案用黑色替換，淺色圖案用白色替換，得到最終的二維碼。激動啊！終於完工！下圖是使用所有 8 種掩模得到的結果，每個 QR 碼都可以掃出 01234567。

到現在我才知道程式沒有寫錯，在沒寫完文章之前，根本沒辦法測試，心裡的一塊石頭終於落地了。要是最終圖案掃碼失敗，真不知道上哪找錯誤去。文章終於寫完，真不容易，學習、查資料、寫作，還得 Coding。還好，文章總算變成成品了，不過程式還沒寫完。現在的程式只夠寫文章用，還要加好多東西。休息，慢慢來吧。