こちらの記事のその後の話。どう
Ulam距離向け誤り訂正符号を構成しようと研究を進めています。
（ちなみに、
上のリンク先では、正確には Levenshtein距離向け誤り訂正符号なのですが、
置換の上では、それらはほぼ同じなので用語を乱用してます。）
先日、私の講義を受講している
大学院生にこの話題を紹介しました。
すると、
「こうすれば、〇〇の構成を一般化できるのでは？」
と、アイデアが返ってきました。
そのアイデアは正しく、新しい符号ができそうです。
いろいろと評価をしたり、そのアイデアを活かすための理論整理が必要なのですが、
うまくいくと予想しています。
やはり、学生と話すのは楽しい。
教員が見えていなかったアイデアを指摘してくれる。
最近、力を入れて研究しているテーマ、それが
Ulam距離向け誤り訂正符号
です。
簡単に言うと、
窓表示で表示した置換に対する削除誤りに耐性を持つ置換集合を作る
ということ。
例えば、５次の置換の部分集合を { [1,2,3,4,5], [5,4,3,2,1] } の２元からなる集合とします。
そこで問題：
数列 [ 2, 3, 4, 5 ]は、先の２元集合の元の成分の一部を削除したものです。
二つのうち、どちらでしょうか？
答えは、[1,2,3,4,5]の方です。これの最初の成分[1]を削除したら、[2,3,4,5]になります。
ちなみに、[5,4,3,2,1]から何かを削除しても、[2,3,4,5]にはなりません。
続いて問題：
数列 [1] は、先の２元集合のどちらかの元の一部を削除してものでしょう？
答えは、二つの元どちらも、です。
[1,2,3,4,5]の後ろの４つの成分[2,3,4,5]を削除しても、
[5,4,3,2,1]の最初の４つの成分[5,4,3,2]を削除しても、
どちらも[1]になります。
いま考えているのは、
n次の置換の部分集合で、 n/2 個の成分を削除しても、一意に元に戻せる集合を作る
という問題。
文献調査の中で、この分野のパイオニア的な仕事である、
Levenshteinの論文
On perfect codes in deletion and insertion metric,
Discrete Mathmatics and Applications, vol.2, no.3, pp.241-258, 1992.
を読みました。
これが、凄い面白い。
感動した。
この理論を土台に拡張したい。
でも、難しい。
そんな毎日を過ごしています。
さて、写真のコーナー。
なぜか、１つのロープだけに群がる鳥たち。
なぜ？？
