- 著者
- 中村博文
- 出版者
- 独立行政法人 国立高等専門学校機構 都城工業高等専門学校
- 雑誌
- 都城工業高等専門学校研究報告 (ISSN:24321036)
- 巻号頁・発行日
- vol.52, pp.69-80, 2018 (Released:2018-03-30)
あらまし 本論文は、記録や通信におけるデータの修復が、実際には計算でなされていることについて、 小学校で習う剰余計算の学習のみを前提として、10~15 分でデモンストレーションする例の報告である。 具体的には、数枚のトランプの並びの中で1 枚分の取り替えがあっても、取り替え前を知らない他者が 計算で数を復元できる例を参加者皆で確認し、更に、なぜ復元できるかの理由を参加者皆が納得できるこ とを目指したデモンストレーションである。 本校の毎年の科学イベントとなっている「おもしろ科学フェスティバル」において実施し、剰余計算を 学習済みの小学生から大人までの殆どが内容を理解し納得できている。 記録や通信においてデータの一部が違ってしまう、即ち誤りが生じる、ということは、頻度は低いが日 常的に起こっている。誤り訂正も現代の情報社会を裏方で支えている技術の一つであるが、例えばQR コ ードの一部をわざと隠したり汚したりして難なく読めるという実験をするというようなことでもなけれ ば、データの修復をする誤り訂正技術の存在は意識することさえも難しい。本論文のデモンストレーショ ンは、誤り訂正符号のひとつであるリード・ソロモン符号のアイデアを、トランプの数が13 種類であり 素数であることを利用した具体化と変形により、トランプ数枚の内の1 枚分の誤り訂正の場合において小 学4 年生以上が納得できる内容になっている。決して単純ではないリード・ソロモン符号ではあるが、そ のアイデアを、より知る人の多い、少ない数学的要素に落とし込む挑戦でもある。 キーワード [出前授業,科学イベント,小学生,誤り訂正,リード・ソロモン符号]
- 著者
- 中村博文
- 出版者
- 独立行政法人 国立高等専門学校機構 都城工業高等専門学校
- 雑誌
- 都城工業高等専門学校研究報告
- 巻号頁・発行日
- vol.52, pp.1-10, 2018
Abstract For lossless data compression, an off-line encoding method which has analysis and cutting ofinput symbol string is proposed. The analysis is based on replacement of frequent symbol pairs appearingrepeatedly. By the operation, the encoder does not cut in the symbol string which emerges more frequentlyin the input symbol string. The encode does not send dictionary data to the encoder directly, but sendinformation for construction of dictionary to the encoder. Its decoding can be done fast with one-pathmethod without deep analysis of its input. A set of efficient data structures for the encoding and thedecoding such as hash table, frequency table, and bidirectional list is used. Theoritical proof that theencoding and the decoding can be executed in time O(N) is proved, where N is the size of input data andO(・) is Bachmann-Landau Big O notation. Keywords [Data compression, Most frequent symbol pair, Replacement, Concatenation, Digram ]