CRC 檢查碼我們每天都在用,Ethernet 乙太網路的每個封包(Frame)後方有個 FCS (Frame Check Sequence),可以用來偵測傳輸過程有沒有 0 變成 1、1 變成 0 的錯誤。其使用的演算法為 Cyclic Redundancy Check 循環冗餘校驗,簡稱 CRC。


來源:維基百科 Ethernet Frame

這玩意兒在網路的很底層被處理掉,用來確保最基本的資料傳輸正確性,我們開發一般應用程式不會寫到,甚至不需要搞懂,就像每天儘量按馬桶把手沖水享受清潔便利的生活就好,不需要了解下水道怎麼串接,污水處理廠如何運作。

但就研究演算法的角度,這是個趣的題目,搞懂原理還挺有趣的。(每次看完這類演算法,都不禁要佩服數學家的腦袋,怎麼能想出這麼巧妙的解法)

CRC 運算原理網上教學很多(例如:CRC檢查碼編碼),這裡不多贅述,我對其中有個 Modulo-2 Binary Division (依據 資訊學會電腦名詞譯名,譯為模二二進位除法) 有興趣,其運算規則類似十進位除法,但用 XOR 取代相減,數字不足時不需借位,一般在解說原理時都會手算,如下圖:


圖片來源

看到這裡,大家應該都知道我想做什麼了。是的,身為重度 Coding 成癮者,怎麼放過這個練習機會,當然要寫個程式取代手算囉~

using System.Text.RegularExpressions;
//args = args.Length == 0 ? new[] { "101010100000", "10111" } : args;

if (args.Length < 2)
{
    Console.WriteLine("Syntax: modulo-2-division <dividend> <divisor>");
    Console.WriteLine("Eaxmple: modulo-2-division 1010101 101");
    return;
}
var dividend = args[0];
var divisor = args[1];
var binDigChk = new Regex("^[01]+$");
var msgs = new List<string>();
if (!binDigChk.IsMatch(dividend))
    msgs.Add("dividend must be a binary number");
if (!binDigChk.IsMatch(divisor))
    msgs.Add("divisor must be a binary number");
if (msgs.Count > 0)
{
    Console.WriteLine(string.Join("\n", msgs));
    return;
}
var dividendLen = dividend.Length;
var divisorLen = divisor.Length;
var deltaLen = dividendLen - divisorLen;
msgs.Add(new string(' ', divisorLen) + "+" + new string('-', dividendLen));

// color red, yellow, green, cyan, magenta, blue    
var colorNums = new[] { 31, 33, 32, 36, 35, 34 };
var clrIdx = 0;
Func<int, char, string> colorText = (idx, text) => $"\u001b[{colorNums[idx % colorNums.Length]}m{text.ToString()}\u001b[0m";
Func<int, int, string, string> getPadding = (st, cnt, text) =>
    string.Join(string.Empty, Enumerable.Range(0, cnt).Select(o => colorText(st + o, text == null ? ':' : text[o])).ToArray());

msgs.Add($"{divisor}|{dividend.Substring(0, dividendLen - deltaLen)}{getPadding(0, deltaLen, dividend[divisorLen..])}");

var m = dividend.Substring(0, divisorLen);
var quotient = "";
var indent = new string(' ', divisorLen + 1);
Func<string, string, string> xor = (a, b) =>
    {
        if (a.Length != b.Length)
            throw new ArgumentException("a and b must be the same length");
        return new string(Enumerable.Range(0, a.Length)
            .Select(o => a[o] == b[o] ? '0' : '1').ToArray());
    };

for (var i = 0; i <= deltaLen; i++)
{
    var q = m[0] == '1' ? "1" : "0";
    var p = q == "1" ? divisor : new string('0', divisorLen);
    var remainder = xor(m, p)[1..];
    quotient += q;
    var padding = getPadding(i, deltaLen - i, null!);
    msgs.Add($"{indent}\x1b[38;5;21m{p[..1]}\x1b[0m{p[1..]}{padding}");
    msgs.Add($"{indent}{new string('-', divisorLen)}{padding}");
    indent += " ";
    m = remainder +
        (divisorLen + i < dividend.Length ? dividend.Substring(divisorLen + i, 1) : "");
    if (i < deltaLen)
        msgs.Add($"{indent}{m[..^1]}{colorText(clrIdx++, m[^1])}{getPadding(i + 1, deltaLen - i - 1, null!)}");
    else
        msgs.Add($"{indent}{m}");
}
msgs.Insert(0, $"{new string(' ', divisorLen * 2)}\x1b[38;5;21m{quotient}\x1b[0m");
Console.WriteLine(string.Join("\n", msgs));

邏輯很單純,用程式演練一次手算規則而已,借用昨天說的 ANSI 顏色控制碼技巧,我很假掰地加了彩色數字對齊標線。大部分手算會省略第一碼是 0 的回合,我選擇如實輸出,並將數字標上鮮藍色與商數的每一位對映。

成果如下,薑薑薑講~~~

另外,VSCode Intellisense 教我一個新寫法,str.Substring(0, 1) 可以寫成 str[..1],str.Substring(1) 可寫成 str[1..],取最後一個字元可以寫 str[^1],str.Substring(0, str.Length -1) 則可寫成 str[..^1]。寫法相對簡潔,但不熟悉C# 陣列索引範圍語法的話,多看幾次才會習慣,學會活用這個 C# 8 加入的新特性,是本次的額外收獲。

A little C# example to demostrating the modulo 2 divsion calculation of CRC.


Comments

Be the first to post a comment

Post a comment