鱗目界域-龍論壇

Amorphous

虺龍

Registered: 2024-06-03

Posts: 25

回应： 龍語文字構造討論

當然是存在的！  

    例如，我使用這樣的一種方法：

    鑑於用爪子在木材上寫字實際上是一件很麻煩的事情（木材的紋理走向導致各個方向的阻力不一致，沒法好好寫字），我只使用最簡單的兩種符號：1和x，這樣刻起來簡單，而且又好認。（後面爲了計算方便，將x寫作0）

    假設我們一次傳遞四個字（位）的信息，爲了滿足容錯的要求，我們需要多餘的三個字來補充，最後，文字的形式是：

d1 d2 d3 d4 p1 p2 p3

    然後規定使用這樣的方法來計算p1,p2和p3，其中的加法的結果是不進位並對2取餘數的，也就是：

1 + 0 = 1
1 + 1 = 0
0 + 0 = 0

p1 = d2 + d3 + d4
p2 = d1 + d3 + d4
p3 = d1 + d2 + d4

現在，假設我需要實際寫出的文字是：

1 0 1 0

現在我們計算p1 p2 p3，

p1 = 0 + 1 + 0 = 1
p2 = 1 + 1 + 0 = 0
p3 = 1 + 0 + 0 = 1

附加在d位的後面，得到最終寫成的文字：

1 0 1 0 1 0 1

好了，現在讓我們嘗試模糊（消失）其中的一位，例如讓0被看錯成1,反之亦然。

一共有7種出錯情況，讓我們分兩類討論。

當看錯的是d位的時候：
使用d1舉例：
現在，我們錯誤地讀取了：

0 0 1 0 1 0 1

讓我們重新計算p1 p2 p3，得到的結果是：

0 0 1 0 1 1 0

可以看到三個p位中只有p1的值符合，而p2 p3都不符合，這說明p1計算過程中不包含而p2 p3計算包含的位發生了錯誤，查看等式發現是d1（因爲p1計算等式中沒有出現d1，而p2 p3中出現了），因此，將d1反轉即可解讀正確的文字：

1 0 1 0

同理，出錯在d2 d3位上的錯誤也可以這樣被修正。
進一步，如果p1 p2 p3 的值都不符合，這提示我們出現錯誤的是d4，將d4反轉即可得到正確的信息。

當錯誤的是p位的時候：
因爲規定了至多一位出錯，所以p1 p2 p3中必定只有一個p的值與計算結果不符合，這種情況下說明錯誤肯定出現在p位，沒有影響到我們實際的前四位信息，可以直接讀出信息。
例如當錯誤出現在p1時，我們讀到：

1 0 1 0 0 0 1

而根據計算，應當是：

1 0 1 0 1 0 1

一個p位不符，出錯肯定在p位上，直接讀取前四位即可。

    總之，通過這種方法，我們做到了即使14%的文字出錯，其中的信息仍然能夠被正確讀取。
    對於你的擴展問題：很容易看出如果我們要求更高的容錯率，只需要增加p位即可，20%完全可以做到，只要你留下足夠的冗餘位用於糾錯。

    實際上，你的問題可以理解爲：能否在一條帶寬無限大的信道上，找到一種無誤碼的編碼方式，而信息論指出：當信號傳輸速率尚未達到香農極限時，可以找到零錯誤率的編碼方法，在這裏你實際上沒有限制信道的帶寬（也就是我能寫多少個字），所以本質上這是一條無限大帶寬的信道，因此，只要錯誤率不是100%，一定可以找到零錯誤的編碼方式。

---

有 1 位朋友喜欢这篇文章：龍爪翻書

---

\normalsize\textbf{Nothing in life is to be feared, it is only to be understood.}\\
\normalsize\textbf{Now is the time to understand more, so that we may fear less.} \\

Amorphous

虺龍

Registered: 2024-06-03

Posts: 25

回应： 龍語文字構造討論

[↑] @Saphira 寫道:   單字目前來看確實不難，消失10%不影響辨認。 難的是句子和更長的段落，集中消失10%有可能消失的是佔面積較小的字，易改變原文意思。 …

    不過，其實也不難，如果你的需要是能夠應對無限長的文字任意部分不可辨認，仍然能夠正常讀取的話，那麼我還可以想到這樣的一種方法    ：

    仍然，我們假設只使用兩種文字，發送的信息是:1 0 1

    首先，讓我們對文字按照位進行遞增編號，假設我們要傳達的是：

编号：0 1 2
信息：1 0 1

    然後，我們來找出一個係數對2取餘數的多項式，使得：
當 x 取編號的值時，多項式的值(模2)與信息對應位的值相等。

找出這種多項式的方法如下：

對於所有信息位爲 1 的第i位，對於非i的所有編號，計算所有下面式子的乘積：

(x-除了i的所有编号)/(i - 除了i的所有编号)

然後將所有信息位爲 1 的位計算出的結果全部相加。

例如，在給出的信息中，第0位和第2位的信息爲1，所以我們需要對這兩位進行計算：

i = 0
l(0) = (x-1)*(x-2)/(0-1)(0-2) = (x^2-3x+2)/2
i = 2
l(2) = (x-0)*(x-1)/(2-0)(2-1) = (x^2-x)/2

然後我們將所有的l相加，得到

F(x) = (2x^2 -4x +2 )/2 = x^2 -2x + 1

然後記得將多項式的係數對2取餘數來簡化運算：

F(x) = x^2 + 1 (x项的系数对2取余数得0所以没了)

我們可以檢驗一下，此時得到的F(x) = x^2 + 1這個多項式在x取編號的值的時候，所得到的值（對2取餘）就是信息的值：

F(0) = 0 + 1 = 1
F(1) = 1 + 1 = 2 对2取余数 = 0
F(2) = 4 + 1 = 5 对2取余数 = 1

可見得到的值是完全正確的，現在，假設我們需要在k位信息損壞後仍然可以讀取信息，我們將編號延長k，並且將每一個延長的編號代入F(x)來得到多餘的信息的值。
例如我們讓k=1：
F(3) = 9 + 1 對2取餘數 = 0
所以有：

编号：0 1 2 3
信息：1 0 1 0

現在，我們完成了書寫信息的部分。

    現在讓我們引入損壞，並嘗試解讀信息。當然，如果是多餘的信息位損壞了，自然不用管，直接讀取信息位即可，而如果有一個信息位被損壞，我們則可以再次執行剩下的三位重複之前的找出多項式的算法：
例如：第0位不可辨認：

编号：0 1 2 3
信息：? 0 1 0

現在，只有第2位信息爲1，於是我們忽略第0位，對這一位進行計算：

i = 2
l'(2) = (x-1)(x-3)/(2-1)(2-3) = (x^2 + 4x + 3)/(-1)
F(x) = l'(2) = x^2 + 1 (对2取余)

可見，我們成功地恢復了多項式，然後，對於丟失的第0位，將x=0代入F(x)得到F(0) = 1：

编号：0 1 2 3
信息：1 0 1 0

我們成功恢復了損壞的信息。

    可見，這個方法可以非常方便地將任意長度(m)位的信息擴展爲m+k位，其中在任意位置丟失不超過k位信息即可還原原始信息。

    實際上，這個方法的原理使用了多項式函數的性質，我們實際上將m位信息看作了一個多項式函數在0到m-1處的取值，然後使用了修改版的拉格朗日插值法，找到了一個滿足這些位置處的取值，並且次數不超過m-1次的唯一的多項式（相當於將信息編碼在了多項式上），然後對這個多項式過採樣了k個樣本。根據多項式函數的性質，可以使用這m+k個樣本中的任意m個樣本，再次使用拉格朗日插值恢復原始的多項式，進而通過代入的方法恢復任意位上的信息，但是，直接使用拉格朗日插值法有可能會得到係數很大的多項式，將值代入會造成很大的空間浪費，因此我這裏其實還利用了模p有限域來剔除不必要的信息，這裏p爲了計算方便取的是2，並且因此假設語言中只有兩個字母，因此其實這個方法可以擴展到有任意多字母的文字上，例如英文有26個字母，這種情況下可以選擇使用大於26的最近的質數作爲模數進行取餘，例如29。

---

有 3 位朋友喜欢这篇文章：龍爪翻書, shiningdracon, 羽落

---

\normalsize\textbf{Nothing in life is to be feared, it is only to be understood.}\\
\normalsize\textbf{Now is the time to understand more, so that we may fear less.} \\

Amorphous

虺龍

Registered: 2024-06-03

Posts: 25

回应： 龍語文字構造討論

@Lunamis午月 寫道: 好奇這種內容算不算密碼學。最近對密碼相關的內容稍微瞭解了一點發現完全是打開新世界大門啊！

    其實是不算的，儘管它的確使用了與密碼非常相似的數學知識，但是他們的目的是完全相反的  ，一個是爲了一定程度增強信息之間的關聯，從而在丟失一部分時可以恢復，另一個是爲了讓信息之間產生儘可能複雜的關係，從而讓分析變得幾乎不可能。

    不過，很高興你會去了解這些知識，在當前的時代，對密碼的基本瞭解是很有必要的，這是在當前的時代中保護個龍隱私強而有力的手段。  

---

\normalsize\textbf{Nothing in life is to be feared, it is only to be understood.}\\
\normalsize\textbf{Now is the time to understand more, so that we may fear less.} \\

Amorphous

虺龍

Registered: 2024-06-03

Posts: 25

回应： 龍語文字構造討論

@Saphira 寫道: 判斷原來的信息不是010x而是x010？

    如果按照你的這種計算方式的話，他不能判斷，在統計錯誤對信息的影響時，一般認爲每位信息只會損壞，但是不會缺失。並且每個位本身的位置是能夠確定的，這種處理方式讓我們能夠更專注於分析其根本的原理。
    你給出的010x和x010已經說明了問題，即使只討論這兩種情況，就一共已經有對應了原始信息的四種可能性了，相當於有兩位錯誤，但是冗餘位只有一位，因此，糾錯最多隻能消除兩種可能性，所以會得到兩個可能的結果。
    但是，位置，本質上也是信息，因此這種情況可以規約到每個位本身確定的情況，正如你加入了位置不確定的條件，實際上可以規約到發送5位信息錯誤2位，實際錯誤率爲40%，超過了之前方法糾錯25%的能力範圍，這是不能糾錯的根本原因。

    因此，如果要求不同步（不能確定信息開始的位置）仍然能夠解碼，我們必須增加位數，同時，爲了實際使用考慮，你需要考慮如何驗證解碼出的信息的正確性的問題，我在此給出一個比較簡單粗暴的解決方案，能夠同時解決這兩個問題。

    不改動先前的方法，而是修改所發送的信息，最簡單的方法例如在每次的原始信息後面添加32個1，這種情況下，你可以嘗試n-1次解碼（假設前導位最多丟失n位），但是儘量均勻選擇，並且不要選擇這些連續的1所在的位置，否則校驗強度會下降，直到解碼出後面以32個1結尾的信息，我在這裏假設多項式插值的性質導致從錯誤的位置開始解碼往往得到的是均勻、混沌、隨機的結果，因此，出現32個1的可能性大約是(n-1)/2^32，大概在42億次解碼中才能誤打誤撞解密出錯誤的信息，其他情況可以被我們通過後面沒有32個1的方式過濾掉，同樣這樣做的一個好處是假設錯誤不密集出現在32個1的位置上，你可以使用最大似然估計來猜測信息開始的位置，減少一部分計算。（這個方法看起來簡單，但是實際上存在風險：如果你故意選擇到了這32個1進行解碼，那麼一定會得到可以通過校驗的錯誤結果）

    但是，如果你需要更強的驗證，你可以將這32個1改爲前面所有信息位輸入一個雜湊算法得到的摘要，你可以認爲基本只有相同的信息才能得到相同的摘要，這裏你可以使用SHA2-256作爲計算摘要的雜湊算法，它輸入（基本）任意長度信息，輸出256位結果，分佈非常均勻，發生錯誤解碼，並且解碼出的信息的摘要值剛好是後面填充的這256位數(這是這個方法強的根本原因)的可能性約爲（這裏是抗原像碰撞性）(n-1)/2^256，這個數字是一個貨真價實的天文數字，你可以認爲錯誤解碼事實上不可能發生。

    現在，從何處開始解碼以及解碼後如何校驗的問題已經解決了。

---

有 1 位朋友喜欢这篇文章：Saphira

---

\normalsize\textbf{Nothing in life is to be feared, it is only to be understood.}\\
\normalsize\textbf{Now is the time to understand more, so that we may fear less.} \\