チェックサム単語

チェックサム

チェックサム(checksum)とは、総和を調べることにより手軽にエラーチェックする手法のことである。

概要

例として文字列「#nicopedia」について考える。

この文字列を送信したり記録したりする際に何らかの要因でデータが書き換わっていたとき、それに気づけないと困ってしまうだろう。そこで文字列についての総和をとることにより調べられるようにする。

ここでは文字列「#nicopedia」をASCIIにおける数値に変換して足し算する。(ここの足し算のやり方は他のやり方でもよい)

文字 # n i c o p e d i a 合計
ASCII 35 110 105 99 111 112 101 100 105 97 975

さらにこの情報を1バイトで扱えるように、256で割った余り情報として加えるようにしよう。
  975÷256 = 3余り207
よって「207」という情報を「#nicopedia」という文字列に付け加えるようにする。(ちなみにこの「207」のような合計値のことをチェックサムと呼ぶ場合も多いので各自文脈で判断してほしい)

さて、このときチェックサム「207」が保たれたまま文字列が「#Nicopedia」にざんされたとする。n, Nに対応するASCIIの値はそれぞれ110, 78(32減っている)なので、文字列の合計値は32減って943。さらに256で割った余り32減って175となる。これは207と一致しないので元の文字列とは異なることが分かる。

チェックサムが一致していてもデータが保たれているとは限らないが、チェックサムが一致しないときデータは確実に間違っている。数学的に考えると自明である命題
  「同じデータならばチェックサムは一致する」
対偶である
  「チェックサムが一致しないならば異なるデータである」
も同様にであると言える。

先述したとおりチェックサムが一致してもデータが保たれているとは限らない。上記の単純な足し算による例ならば、チェックサムを一致したままデータざんする簡単な方法は「単純な入れ替え」である。上記で用いた「#nicopedia」という文字列はいくら入れ替えたところで総和が975であり、256で割った余り207である。

さらに、総和さえ合っていれば何をしてもよいので上手にざんすれば何事もなかったかのようにチェックを通過できる。

そのうえ故意ではなくても偶然チェックサムが一致してしまう可性だってある。先程の例のように1バイトデータを付加する場合、単純計算で1/256確率で一致してしまう。これは状況によっては視できない確率といえるだろう。

このようにチェックサムはエラーを検出する方法としては手軽であるが信頼性は高いとは言い切れない。「誤り検出」などのキーワード検索するとより良い手法がたくさん見つかるだろう。

実例

バーコード

日本におけるバーコードの種類はいくつかあるが、ここでは

の13桁のバーコードについて考える。(他の場合についても本質はほぼ変わらない)

コード日本45または49であるから今回は45として、メーカコードと商品コード適当1234567890にして残りのチェックディジットを計算していく。バーコードに書くと
  4  5123467890?
といった具合である。(?の部分がチェックディジットに当たる)

このタイプバーコードのチェックディジットの計算には「モジュラス10ウェイト3」という手法が使われる。modulusとは剰余の計算で用いる「法」であり、「10を法とする…」や「mod10」のことである。weightとは計算する際の「重み付け」のことであり今回は特定の桁を3倍する。

「モジュラス10ウェイト3」の計算方法は次の通りである。

  1. チェックディジットを除いた数字に対し先頭を1桁として奇数桁と偶数桁に分ける
  2. 奇数桁の数値を合計し3倍する
  3. 偶数桁の数値を合計する
  4. 2と3でめた値を合計し一の位の10の補数が答え(すなわち次の10の倍数までの値)

具体的に見ていこう。

バーコード 4 5 1 2 3 4 5 6 7 8 9 0 合計
奇数 5 2 4 6 8 0 25
偶数 4 1 3 5 7 9 29

  25×3+29=104
なので、めるチェックディジットは6となった。よってバーコード
  4 512345 678906
となる。

かなり複雑な計算をしたが、本質的な部分である
  「チェックサムが一致しないならば異なるデータである」
の部分はきちんと成立しており、適当バーコードの値をざんしたとしても約9割の確率で発見できる。

サブフレームリセット

サブフレームリセットとは、ゲームにおいて機械語1命単位の任意のタイミングリセットを行う技のことである。

これをセーブデータの書き込みの最中に行うと、通常はデータが中途半端な書き込みで終了し"データが破損した"状態になる。(一般にデータが破損した状態だと判定されるとデータは消去される)

ところでデータが破損した状態というのはどうやって判定されるのだろうか?この判定にチェックサムが使われる場合が多い。そして先述の通りチェックサムは総和さえ合っていれば何をしてもよい。すなわちあらかじめチェックサムを通るように準備してサブフレームリセットを行えばとんでもないデータざんを行うことが可である。

従来のエミュレータは1フレームごとに操作を受け付けるものであったため、サブフレームリセットは実機でのみ(理論上は)可である行動として提唱されていた。ただし、実機でサブフレームリセットを行おうとすると、状況にもよるが1ミリ未満のシビアなタイミングを要される。その後TASエミュレータであるLsnesサブフレームリセットに対応(Lsnes上の名称はDelayed Reset)すると、TASにおける記録更新の手法として用いられるようになった。特に人間の手では困難だったシビアなタイミングでのリセットの問題はTASでは問題にならないため、チェックサムを通過しつつ最速をすというシンプル(かつそれはそれで困難)な問題へと変えることが可になった。

関連動画

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%81%E3%82%A7%E3%83%83%E3%82%AF%E3%82%B5%E3%83%A0

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

チェックサム

まだ掲示板に書き込みがありません…以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • チェックサムについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!