スレッドNo.2353

RE:13個の金貨13人の技術者

[2305]の続きです。

13人いればそのうち最大２名が嘘をついても64枚の金貨を処理できるだろう、の件です。

既にお示ししましたように、知人から解を教えてもらったもののその背景には何が有るのか解らずに彷徨っております。
普通に作ると32枚が限界。

漸くこのほど古い論文をみつけました。
An optimum nonlinear code
code
Alan W. Nordstrom ,
John P. Robinson

https://www.sciencedirect.com/science/article/pii/S0019995867908352

これに書いてあることを猿真似して
最小ハミング距離が5でありながら14ビットで128もの符号語数を実現する方法をメモしておきたく存じます。

情報ビットが7、冗長ビットが7、前者をX,後者をYとしたときに、エンコード方法は以下となります。
なお、「⊕」は排他的論理和、「 ⋅ 」は論理積です。

X₀∥X₁∥X₂∥X₃∥X₄∥X₅∥X₆
⇒
X₀∥X₁∥X₂∥X₃∥X₄∥X₅∥X₆∥Y₀∥Y₁∥Y₂∥Y₃∥Y₄∥Y₅∥Y₆

ただし、
Y₀ = X₆ ⊕ X₀ ⊕ X₁ ⊕ X₃ ⊕ ((X₀ ⊕ X₄) ⋅ (X₁ ⊕ X₂ ⊕ X₃ ⊕ X₅)) ⊕ ((X₁ ⊕ X₂) ⋅ (X₃ ⊕ X₅))

Y₁ = X₀ ⊕ X₁ ⊕ X₂ ⊕ X₄ ⊕ ((X₁ ⊕ X₅) ⋅ (X₂ ⊕ X₃ ⊕ X₄ ⊕ X₆)) ⊕ ((X₂ ⊕ X₃) ⋅ (X₄ ⊕ X₆))

Y₂ = X₁ ⊕ X₂ ⊕ X₃ ⊕ X₅ ⊕ ((X₂ ⊕ X₆) ⋅ (X₃ ⊕ X₄ ⊕ X₅ ⊕ X₀)) ⊕ ((X₃ ⊕ X₄) ⋅ (X₅ ⊕ X₀))

Y₃ = X₂ ⊕ X₃ ⊕ X₄ ⊕ X₆ ⊕ ((X₃ ⊕ X₀) ⋅ (X₄ ⊕ X₅ ⊕ X₆ ⊕ X₁)) ⊕ ((X₄ ⊕ X₅) ⋅ (X₆ ⊕ X₁))

Y₄ = X₃ ⊕ X₄ ⊕ X₅ ⊕ X₀ ⊕ ((X₄ ⊕ X₁) ⋅ (X₅ ⊕ X₆ ⊕ X₀ ⊕ X₂)) ⊕ ((X₅ ⊕ X₆) ⋅ (X₀ ⊕ X₂))

Y₅ = X₄ ⊕ X₅ ⊕ X₆ ⊕ X₁ ⊕ ((X₅ ⊕ X₂) ⋅ (X₆ ⊕ X₀ ⊕ X₁ ⊕ X₃)) ⊕ ((X₆ ⊕ X₀) ⋅ (X₁ ⊕ X₃))

Y₆ = X₅ ⊕ X₆ ⊕ X₀ ⊕ X₂ ⊕ ((X₆ ⊕ X₃) ⋅ (X₀ ⊕ X₁ ⊕ X₂ ⊕ X₄)) ⊕ ((X₀ ⊕ X₁) ⋅ (X₂ ⊕ X₄))

とします。
これをプログラムで実装して出力したところ確かに所望のものができました。
よもやよもや論理積が使われているとは……

エンコード後にX₀が0のものだけを取り出すと64件の符号語数となり、X₀はダミーと成り下がりましたのでこれを除去すれば、符号長が13、最小ハミング距離が5となります。これで私が欲しかった実物を得ることができました。
0000000000000
0000011001011
0000100010111
0000111100110
0001000101110
0001011111000
0001101001101
0001110100001
0010001011100
0010010101101
0010101110001
0010110111010
0011000011011
0011011110111
0011101000010
0011110010100
0100000111001
0100011010101
0100101011010
0100110001100
0101001100011
0101010010010
0101101110100
0101110111111
0110000110110
0110011100000
0110101101111
0110110000011
0111000000101
0111011001110
0111100101000
0111111011001
1000001110010
1000010011110
1000100101011
1000111111101
1001000110101
1001011000100
1001100011000
1001111010011
1010001000111
1010010010001
1010100100100
1010111001000
1011001101001
1011010100010
1011101111110
1011110001111
1100001101100
1100010100111
1100101000001
1100110110000
1101001011111
1101010001001
1101100000110
1101111101010
1110000001010
1110011111011
1110100011101
1110111010110
1111001010000
1111010111100
1111100110011
1111111100101

No.2353Dengan kesaktian Indukmu12月1日 18:05

このスレッドに返信

お名前
URL
メッセージ

> "Dengan kesaktian Indukmu"さんが書かれました:
> [2305]の続きです。

> 13人いればそのうち最大２名が嘘をついても64枚の金貨を処理できるだろう、の件です。

> 既にお示ししましたように、知人から解を教えてもらったもののその背景には何が有るのか解らずに彷徨っております。
> 普通に作ると32枚が限界。

> 漸くこのほど古い論文をみつけました。
> An optimum nonlinear code
> code 
> Alan W. Nordstrom ,
> John P. Robinson

> https://www.sciencedirect.com/science/article/pii/S0019995867908352

> これに書いてあることを猿真似して
> 最小ハミング距離が5でありながら14ビットで128もの符号語数を実現する方法をメモしておきたく存じます。

> 情報ビットが7、冗長ビットが7、前者をX,後者をYとしたときに、エンコード方法は以下となります。
> なお、「⊕」は排他的論理和、「 ⋅ 」は論理積です。

> X₀∥X₁∥X₂∥X₃∥X₄∥X₅∥X₆
> ⇒
> X₀∥X₁∥X₂∥X₃∥X₄∥X₅∥X₆∥Y₀∥Y₁∥Y₂∥Y₃∥Y₄∥Y₅∥Y₆

> ただし、
> Y₀ = X₆ ⊕ X₀ ⊕ X₁ ⊕ X₃ ⊕ ((X₀ ⊕ X₄) ⋅ (X₁ ⊕ X₂ ⊕ X₃ ⊕ X₅)) ⊕ ((X₁ ⊕ X₂) ⋅ (X₃ ⊕ X₅))

> Y₁ = X₀ ⊕ X₁ ⊕ X₂ ⊕ X₄ ⊕ ((X₁ ⊕ X₅) ⋅ (X₂ ⊕ X₃ ⊕ X₄ ⊕ X₆)) ⊕ ((X₂ ⊕ X₃) ⋅ (X₄ ⊕ X₆))

> Y₂ = X₁ ⊕ X₂ ⊕ X₃ ⊕ X₅ ⊕ ((X₂ ⊕ X₆) ⋅ (X₃ ⊕ X₄ ⊕ X₅ ⊕ X₀)) ⊕ ((X₃ ⊕ X₄) ⋅ (X₅ ⊕ X₀))

> Y₃ = X₂ ⊕ X₃ ⊕ X₄ ⊕ X₆ ⊕ ((X₃ ⊕ X₀) ⋅ (X₄ ⊕ X₅ ⊕ X₆ ⊕ X₁)) ⊕ ((X₄ ⊕ X₅) ⋅ (X₆ ⊕ X₁))

> Y₄ = X₃ ⊕ X₄ ⊕ X₅ ⊕ X₀ ⊕ ((X₄ ⊕ X₁) ⋅ (X₅ ⊕ X₆ ⊕ X₀ ⊕ X₂)) ⊕ ((X₅ ⊕ X₆) ⋅ (X₀ ⊕ X₂))

> Y₅ = X₄ ⊕ X₅ ⊕ X₆ ⊕ X₁ ⊕ ((X₅ ⊕ X₂) ⋅ (X₆ ⊕ X₀ ⊕ X₁ ⊕ X₃)) ⊕ ((X₆ ⊕ X₀) ⋅ (X₁ ⊕ X₃))

> Y₆ = X₅ ⊕ X₆ ⊕ X₀ ⊕ X₂ ⊕ ((X₆ ⊕ X₃) ⋅ (X₀ ⊕ X₁ ⊕ X₂ ⊕ X₄)) ⊕ ((X₀ ⊕ X₁) ⋅ (X₂ ⊕ X₄))

> とします。
> これをプログラムで実装して出力したところ確かに所望のものができました。
> よもやよもや論理積が使われているとは……

> エンコード後にX₀が0のものだけを取り出すと64件の符号語数となり、X₀はダミーと成り下がりましたのでこれを除去すれば、符号長が13、最小ハミング距離が5となります。これで私が欲しかった実物を得ることができました。
> 0000000000000  
> 0000011001011  
> 0000100010111  
> 0000111100110  
> 0001000101110  
> 0001011111000  
> 0001101001101  
> 0001110100001  
> 0010001011100  
> 0010010101101  
> 0010101110001  
> 0010110111010  
> 0011000011011  
> 0011011110111  
> 0011101000010  
> 0011110010100  
> 0100000111001  
> 0100011010101  
> 0100101011010  
> 0100110001100  
> 0101001100011  
> 0101010010010  
> 0101101110100  
> 0101110111111  
> 0110000110110  
> 0110011100000  
> 0110101101111  
> 0110110000011  
> 0111000000101  
> 0111011001110  
> 0111100101000  
> 0111111011001  
> 1000001110010  
> 1000010011110  
> 1000100101011  
> 1000111111101  
> 1001000110101  
> 1001011000100  
> 1001100011000  
> 1001111010011  
> 1010001000111  
> 1010010010001  
> 1010100100100  
> 1010111001000  
> 1011001101001  
> 1011010100010  
> 1011101111110  
> 1011110001111  
> 1100001101100  
> 1100010100111  
> 1100101000001  
> 1100110110000  
> 1101001011111  
> 1101010001001  
> 1101100000110  
> 1101111101010  
> 1110000001010  
> 1110011111011  
> 1110100011101  
> 1110111010110  
> 1111001010000  
> 1111010111100  
> 1111100110011  
> 1111111100101

画像
編集キー
投稿前にプレビューを確認

ご利用のブラウザはJavaScriptが実行できません。
この掲示板に投稿するには、JavaScriptが実行できるブラウザでアクセスする必要があります。

😊出会いの泉😊