誤り検出訂正のソースを表示
←
誤り検出訂正
移動先:
案内
、
検索
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''誤り検出訂正'''(あやまりけんしゅつていせい)または'''エラー検出訂正''' (error detection and correction)とは、[[データ]]に'''符号誤り'''(エラー)が発生した場合にそれを検出、あるいは検出し訂正することである。検出だけをする'''誤り検出'''または'''エラー検出'''と、検出し訂正する'''誤り訂正'''または'''エラー訂正'''を区別することもある。誤り検出訂正により、[[記憶装置]]や[[デジタル]]通信・信号処理の信頼性が確保されている。 == 誤り検出と誤り訂正 == 一般に誤り検出訂正では、k 単位長(k [[ビット]]、k [[バイト (情報)|バイト]] など)の符号を、n = m + k 単位長の符号語に変換する。これを (n, k) 符号、あるいは、符号形式を添えて (n, k) ××符号などと呼ぶ(誤り訂正符号を特に'''ECC'''と略す)。符号語は、最小[[ハミング距離]]が d > 1、つまり、互いに少なくとも d 単位が異なっていて、この[[冗長性 (情報理論)|冗長性]]を利用して誤り検出訂正がなされる。dを添えて、 (n, k, d) 符号ともいう。 適切な (n, k, d) 符号は、符号語あたり d - 1 単位の誤りを検出でき、[(d - 1) / 2] 単位([ ] は[[床関数]])の誤りを訂正できる。d ≦ 2 ならば、誤り訂正能力は [(d - 1) / 2] = 0 となり、単なる誤り検出となる。ただし、データの消失に対しては、つまり誤り位置がわかっているときは、d 単位の消失を訂正できる。これを特に、'''消失訂正'''と呼ぶ。単なる誤り訂正も、最低 1 単位の消失訂正能力を持つ。 たとえば、(2, 1, 2) 符号である[[ミラーリング]]は、 * どちらかに誤りが起これば検出できるが、両方に起これば検出できない。(誤り検出能力1) * どちらか(どちらかはわからない)に誤りが起これば訂正できない。(誤り訂正能力0) * どちらかが消失すれば訂正できるが、両方に起これば訂正できない。(消失訂正能力1) となる。(3, 1, 3) 符号である[[一方向誤り訂正#動作原理|三重ミラーリング]]では、誤り検出能力と消失訂正能力が2となり、誤り訂正能力1も得る。 双方向の[[通信]]では、誤り検出さえできれば誤り訂正ができなくても、送信者に再送を要求できれば、実質的に誤りを訂正できる。これを自動的におこなう仕組みを、[[自動再送要求]] (ARQ, Automatic Repeat reQuest) と呼ぶ。 == バースト誤りとランダム誤り == 誤りには、 * 短い区間に多数の誤りが集中するバースト誤り * 散発的に単独で誤りが発生するランダム誤り の2種類がある。 多くの誤り検出・訂正は、全体の誤り率が許容範囲でも、バースト誤りに対しては、1つのブロックに多くの誤りが集中するため、対応できない。そこで、符号の順序を入れ替え、同じブロックのデータを分散させ、バースト誤りが1つのブロックに集中しないようにする。この技術を[[インターリーブ]]という。 == 誤り補正 == 特に音声や映像など、人間の感覚に訴える信号のディジタル化されたデータで真の値から多少の[[誤差]]が許容される場合、誤り検出は可能でも誤り訂正が不可能(訂正能力を超えている)かまたは誤り訂正が実装されていないとき、元のデータ自身に含まれる冗長性を利用して欠落データを予測して置き換えることがある。これを特に'''誤り補正'''(error compensation)と呼んで区別する。補正されたデータは真の値と一致するとは限らないが、真の値から許容される誤差内にあると期待される。[[コンパクトディスク|CD]]などでは、誤り補正がデータ読み取り誤りに対する「最後の手段」として使われている。 誤り補正では、一般には、近傍の標本に重み付けをした和、すなわちフィルタを畳み込んだ値を予測値(補正値)とする。特に、直前・直後の標本を使うものを、以下のように呼ぶ。 : <math>x_n = \frac{1}{2} (x_{n - 1} + x_{n + 1})</math> - 平均値補間 : <math>x_n = x_{n - 1} \,</math> - 前値ホールド : <math>x_n = x_{n + 1} \,</math> - 後値ホールド 誤り補正は原信号自身に含まれる冗長性を使うため、[[データ圧縮]]、特に[[非可逆圧縮]]と同種の原理に基づいている。 == 誤り検出・訂正の例 == === 誤り検出 === * [[ブロック符号]] ** 2重化 *** [[バックアップ]] *** [[ミラーリング]] - [[RAID]]-1 *** [[一方向誤り訂正]] (FEC, forward error correction) ** [[パリティビット|パリティ符号]](パリティチェック) - [[シリアル通信]]、RAID-3/4/5/6 *** [[垂直パリティチェック]] (VRC) *** [[水平パリティチェック]] (LRC) ** [[定比率符号]](l out of n 符号) ** [[チェックサム]] *** [[群計数チェック]] *** [[Luhnアルゴリズム]] ** [[巡回符号]] *** [[巡回冗長検査]] (CRC) - [[フロッピーディスク]]、[[ユニバーサル・シリアル・バス|USB]] ** [[ハッシュ関数]](主に[[暗号理論|暗号]]用) *** [[MD4]] *** [[MD5]] *** [[Secure Hash Algorithm]] - [[SHA-1]] - [[SHA-2]] (SHA-224, SHA-256, SHA-384, SHA-512) - [[SHA-3]] === 誤り訂正 === * ブロック符号 ** 多重化 *** 反復符号 (repetition code) ** 縦横パリティ ** [[ハミング符号]] - [[Random Access Memory|RAM]]、RAID-2 ** [[巡回符号]] *** [[巡回ハミング符号]] *** [[ゴレイ符号]] **** [[2元ゴレイ符号]] ([[:en:Binary Golay code|binary Golay code]]) *** [[BCH符号]] - 自動車無線(43,31)、衛星ラジオ(63,56) **** [[リード・ソロモン符号]](RS符号、RSC) ***** [[CIRC]]([[:en:Cross-Interleaved Reed-Solomon Coding|Cross-Interleaved Reed-Solomon Code]])- [[コンパクトディスク|CD]] ***** リードソロモン積符号 (RSP符号) - DAT *** [[差集合巡回符号]] **** 短縮化差集合巡回符号 - 文字放送(272,190) *** [[ファイア符号]] - [[ハードディスク]] ** [[疎グラフ符号]] *** [[ターボ符号]] ([[:en:Turbo code|turbo code]]) *** [[低密度パリティ検査符号]] (LDPC) - [[10ギガビット・イーサネット|10GBASE-T]] (IEEE 802.3an)、[[Mobile WiMAX]] (IEEE 802.16e) * [[畳み込み符号]]([[:en:Convolutional code|convolutional code]]) ** [[:en:Hagelbarger code|Hagelbarger code]] ** [[最尤復号符号]]、[[ビタビアルゴリズム]]([[:en:Viterbi Algorithm|Viterbi Algorithm]]) == 関連項目 == * [[改竄]] * [[認証]] * [[ガロア体]] * [[RAID]] * [[チェックディジット]] * [[冗長性 (情報理論)|冗長化]] <!--*[[シャノン限界]]([[:en:Shannon limit|Shannon limit]])--><!--赤リンク--> {{DEFAULTSORT:あやまりけんしゆつ}} [[Category:誤り検出訂正|*]] [[Category:通信工学]] [[Category:安全]] [[Category:数学に関する記事]]
誤り検出訂正
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
sandbox
commonsupload
ヘルプ
ヘルプ
井戸端
notice
bugreportspage
sitesupport
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報