トランプを使ったリード・ソロモン符号の符号化とエラー訂正法入門

 「QR コード」は、「リード・ソロモン符号」による符号化と、リトライ(データ再送)を必要としない前方エラー訂正手順(FEC)を含むプロトコルが使われているとのことです。

従来のシリアル・パケット・データ通信では、データエラーが発生した場合、パケット・フレーム単位のデータ送信をしなおすリトライ手順が使われてきましたが、「QR コード」では、こうした再送が不要となる革新的進歩がありました。

今回は、「リード・ソロモン符号」の入門として、トランプを使ったリード・ソロモン符号の復号化とエラー訂正法入門について、小学校3年生でもわかる簡単なデモ、という紹介の文献[1]を読み、読みにくかった部分をとりだして説明を再構成し、同文献に記述漏れのあった「剰余計算表」を新規考案して提示し、

(1)4枚のカードに、2枚の冗長データ・カードを加える符号化方法

(2)それら6枚のカード中に1枚のカードの数字データが伝送路で化けた場合に、それを訂正する復号化手順

とするデモ実例を以下に要点だけを要約してまとめました。

(1)符号化方法(エンコード方法)

ここでは、次の4個(4バイト)のカード表現のデータに、2個(2バイト)の冗長データを追加した符号を送信するものとする。

・・・以上のように、数字=7 と数字=13 の冗長データが求まったので、先の4個のカードに続けて次のようにカードをつなげる。

ここで、あらかじめ、次の「剰余計算表」を作成しておく。

剰余計算表は次の計算ルールにより作成する。

(A) S1 = mod(a+b+c+d+e+f, 13) ... 数字S1は、カード a+b+c+d+e+f  を計算した整数を、素数13で割った余りの整数

(B) S2 = mod(a+2b+3c+4d+5e+6f, 13) ... 数字S2は、カード a+2b+3c+4d+5e+6f を計算した整数を、素数13で割った余りの整数

(C) T は、データが化けて誤ったカードの位置を意味する整数で、T={1,2,3,4,5,6} の集合で、

　式　S1xT=S2 を満たす。

　剰余計算表

(2)データ・エラー修正の復号化手順

・・・このように、誤ったカード9 を、訂正するカード2 で置き換え、データ修正する。

(3)QR code の生成例

携帯電話の「バーコード」機能で読み取れます。

(デコードの実験時は、２つのQRコードのどちかかを、画面をスクロールして隠して下さい。)

課題：

(1)トランプカードでは、最大の素数が13なので、剰余数は14, 15を仮定せずにすむ。

これが4ビットのデータビット表現BCDコードとした場合、0x00,0x01,..,0x0C,0x0D,0x0E,0x0F

の16種類のパターン数になり、最大数の素数17として剰余数を変更したい。

(2) 項番#(1)に合わせ、剰余計算表を、最大素数17として再定義し、エラー訂正計算アルゴリズムを変更すること。

参考資料:

[1]誤り訂正技術のしくみのデモンストレーション例 

―小学校の剰余計算の学習のみを前提とするリード・ソロモン符号の変形例―

A Demonstration Example of Mechanism of Error Correction ―A Modification of Reed-Solomon Code Assuming Only Learning of Remainder Calculation at Elementary School―

中村博文先生, Hirofumi NAKAMURA (平成 29 年 10 月 2 日)　

(Respective Copyright Reserved)

[2]QR code 概説メモ

https://www.youtube.com/watch?v=x2bqa5yv9KI

[3] オープンソースのQRコードライブラリ開発プロジェクト

https://qrcode.osdn.jp/

履歴：

0.1 : 2021/01/10  

最大数の素数17として剰余数を変更するアルゴリズム変更について課題を追記。  

0.2 :2023/11/12

ETV メモ動画追加。オープンソース QRコード開発プロジェクトのリンク追加。

ブログ記事目次へ戻る