跳到主要內容
影片

QR 碼是怎麼運作的:為什麼撕破的碼還能掃

QR 碼存的不只是訊息本身,還有根據它算出來的備用位元組,所以被撕破、弄髒或被 logo 蓋住的位元組,掃描器都能重建。四個糾錯等級,約 7% 到 30% 的碼字,還有三個不能蓋住的角方塊。一支 48 秒的科普短片,每個數字都有出處。

發布於
閱讀
約 7 分鐘
標籤
  • qr-codes
  • how-it-works
  • explainer
目錄
  1. 撕破了、弄髒了,照樣能掃
  2. 備用位元組,由訊息算出
  3. 每修一個位元組,要兩個備用位元組
  4. 四個等級:7% 到 30%
  5. logo 是它能修的損壞
  6. 別蓋住角
  7. 結論
  8. 來源

一句話總結: QR 碼存的不只是訊息本身。它還會加上根據訊息算出來的備用位元組,也就是里德-所羅門(Reed–Solomon)糾錯,和音樂 CD 用的是同一套數學,所以掃描器能重建缺漏或出錯的位元組。備用位元組多少由你決定:L、M、Q、H 四個等級,分別能復原約 7%、15%、25% 和 30% 的碼字,備用位元組越多,碼就越大。這就是為什麼中間放個 logo 也能掃:對掃描器來說,那只是損壞。三個角上的方塊則不一樣:它們不是資料,而是讓掃描器找到並擺正這個碼,所以大多數掃描器都少不了它們。

撕破了、弄髒了,照樣能掃

QR 碼的開發者 DENSO WAVE(電裝波動):「QR Code has error correction capability to restore data if the code is dirty or damaged.」(QR 碼具有糾錯能力,碼被弄髒或損壞時也能復原資料。)它在特色清單裡還寫道:「Data can be restored even if the symbol is partially dirty or damaged.」(即使符號部分弄髒或損壞,資料也能復原。)

影片裡的碼是真的:內容是 oliverz.dev。一角撕破、邊上有汙漬、中間蓋著 logo,它的 44 個碼字裡有 13 個是錯的,但照樣能解出來(我們用 jsQR 和 ZXing 兩個解碼器測試過)。

備用位元組,由訊息算出

DENSO WAVE:「The QR Code error correction feature is implemented by adding a Reed-Solomon Code… to the original data.」(QR 碼的糾錯功能,是透過在原始資料上加上里德-所羅門碼來實現的。)坎特伯雷大學的《Computer Science Field Guide》說得更簡單:「it adds extra bits to the data so that errors can be corrected.」(它在資料上加了額外的位元,這樣錯誤就能被修正。)

單位是碼字。DENSO WAVE:「codeword is a unit that constructs the data area. One codeword of QR Code is equal to 8 bits.」(碼字是構成資料區的單位。QR 碼的一個碼字等於 8 位元。)CS Field Guide:「Each black or white square (“dot” or “module”) corresponds to one bit of data.」(每個黑色或白色的小方塊(「點」或「模組」)對應一位元資料。)所以八個模組就是一個位元組。

這套數學並不新。DENSO WAVE:「Reed-Solomon Code is a mathematical error correction method used for music CDs etc. The technology was originally developed as a measure against communication noise for artificial satellites and planetary probes.」(里德-所羅門碼是一種數學糾錯方法,用於音樂 CD 等。這項技術最初是為了對付人造衛星和行星探測器的通訊雜訊而開發的。)

每修一個位元組,要兩個備用位元組

DENSO WAVE:「Reed-Solomon Code requires twice the amount of codewords to be corrected.」(里德-所羅門碼需要兩倍於待修正數量的碼字。)CS Field Guide:「The maximum number of errors that a Reed-Solomon code can correct is one half of the amount of extra error correcting data added to it.」(里德-所羅門碼最多能修正的錯誤數,是加進去的額外糾錯資料量的一半。)

我們的碼用最高等級時,有 16 個訊息碼字和 28 個備用碼字,共 44 個。28 的一半是 14,所以它最多能修 14 個錯誤碼字:44 個裡的 14 個約為 32%(我們自己算的),對應 DENSO 的「Approx. 30%」(約 30%)。在我們的測試裡,極限恰好就在這裡:錯 14 個碼字還能讀出,錯 15 個就沒有結果。

是沒有結果,而不是錯誤的結果。CS Field Guide:「they won’t read the data incorrectly, instead they just refuse to give any data at all, rather than giving you incorrect data.」(它們不會把資料讀錯,而是乾脆拒絕給出任何資料,而不是給你錯誤的資料。)

四個等級:7% 到 30%

DENSO WAVE 對標準(ISO/IEC 18004)的概述:「Level L Level M Level Q Level H Approx. 7% of codewords can be restored. Approx. 15% of codewords can be restored. Approx. 25% of codewords can be restored. Approx. 30% of codewords can be restored.」(L 級、M 級、Q 級、H 級:約 7% 的碼字可復原;約 15% 的碼字可復原;約 25% 的碼字可復原;約 30% 的碼字可復原。)

這個百分比算的是碼字,不是你看到的面積:「*Data restoration rate for total codewords」……「QR Code therefore represents its error correction rate as a ratio of the total codewords.」(*資料復原率以全部碼字計……因此 QR 碼用占全部碼字的比例來表示糾錯率。)

備用位元組越多,占的地方越大。DENSO WAVE:「Raising this level improves error correction capability but also increases the amount of data QR Code size.」(提高等級能增強糾錯能力,但也會增加資料量和 QR 碼的尺寸。)還有:「as the amount of data increases, more modules are required to comprise QR Code, resulting in larger QR Code symbols.」(資料量增加時,組成 QR 碼需要更多模組,QR 碼符號也就更大。)我們為 oliverz.dev 產生的四個碼,訊息碼字 + 備用碼字:

  • L:19 + 7,21 × 21 個模組
  • M:16 + 10,21 × 21 個模組
  • Q:13 + 13,21 × 21 個模組
  • H:16 + 28,25 × 25 個模組(在 H 級,「oliverz.dev」的 11 個位元組放不進 21 × 21 了)

logo 是它能修的損壞

所以中間放個 logo 也能掃:掃描器把它當作損壞,把它擋住的內容重建出來。在我們的 H 級碼上,一個 7 × 7 模組的 logo 讓 44 個碼字裡的 9 個出錯,在 14 個的上限之內。

不過這不是白來的:它用掉了備用位元組。DENSO WAVE 的常見問題,談到帶顏色或插圖的碼時說:「If it is deformed, the QR Code's error correction function is invoked where even a tiny missing or smeared part renders the reading operation impossible, or the response of the operation may become slow.」(如果碼變形了,就會動用 QR 碼的糾錯功能,這時哪怕再缺一小塊或糊了一點,也可能讀不出來,或者讀取變慢。)

別蓋住角

三個大方塊不是資料。DENSO WAVE:「QR Code accomplishes this task through position detection patterns located at the three corners of the symbol.」(QR 碼透過位於符號三個角上的位置偵測圖形來完成這項任務。)它講 QR 碼歷史時寫道,有了它們,「the orientation of their code could be determined regardless of the angle of scanning, which could be any angle out of 360°」(無論以什麼角度掃描,360° 中的任何角度,都能確定碼的方向)。

CS Field Guide:「Don’t colour in near the three large squares in the corners, as most QR scanners need these to align the image.」(不要在角上三個大方塊附近塗色,因為大多數 QR 掃描器需要靠它們來對齊影像。)

在我們的測試裡,在一個角方塊中心貼一張 3 × 3 模組的小貼紙,兩個解碼器就都讀不出了,而一個資料位元組都沒碰到。logo 蓋住 49 個模組照樣能掃;貼紙只蓋 9 個,卻掃不出來。

結論

  1. QR 碼存的是訊息加上由它算出的備用位元組(里德-所羅門),所以掃描器能重建被撕破、弄髒或蓋住的位元組。
  2. 備用位元組多少由你選:L、M、Q、H,約 7% 到 30% 的碼字;備用位元組越多,碼越大。中間的 logo 就是備用位元組能彌補的損壞。
  3. 三個角方塊不是資料:它們讓掃描器找到並擺正這個碼,所以大多數掃描器都少不了它們。

來源

影片以程式碼製作動畫,腳本在 AI 協助下撰寫;上面每段引文都對照出處查證過,標註「我們自己算的」的數字是我們自己的計算。碼是真的(先產生,再用 jsQR 和 ZXing 解碼),它們的位元組和碼字數也是真的。示意的部分:撕口、汙漬和 logo(一個通用圖形,正好畫在我們測試過的那些模組上)、相機取景框,以及傾斜的碼(同一個碼按透視畫出)。真實的磨損不會像沿著模組畫的損壞這麼整齊。「QR Code」是 DENSO WAVE INCORPORATED 的註冊商標。影片為英文旁白。影片用 Shotloop 製作:我做的免費 Mac 應用程式,用程式碼做科普短片,一個鏡頭一個鏡頭地修改。

How It Works 更多

YouTube 播放清單 ↗
追蹤我

我會持續分享正在做的專案、實驗和心得。

YouTube 上發影片,X 上發短筆記。這裡的每篇文章都會連結到兩邊。

YouTube