龍語文字構造討論

Saphira · 2024-06-11 17:30:35

前段時間一直在想一個問題：~~衆所周知，龍類一般生活在原生態區域。如果用爪子將文字刻在樹幹或者各類石頭上難免會被環境一定程度侵蝕，破壞文字傳遞的信息。~~是否存在一種文字，可允許其佔有表面積的任意10%消失但不損失信息？

以現實世界的數字舉例，用爪子在樹上寫下"0123456789"（假設每個數字都佔1平方釐米的面積），消失的10%恰好是一個完整數字，那顯然會導致信息損失，故不符合命題。

初步猜想符合命題的文字應注重“計算”，文字的所有部分實際上都參與“推理並檢驗其他部分完整性”這個過程。

拓展問題：能否做到任意消失20%而不損失信息？文字可做到的極限消失率（不損失信息情況下的最大消失面積百分比）是多少？

Amorphous · 2024-06-12 04:56:59

當然是存在的！ [大笑]

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

鑑於用爪子在木材上寫字實際上是一件很麻煩的事情（木材的紋理走向導致各個方向的阻力不一致，沒法好好寫字），我只使用最簡單的兩種符號：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%，一定可以找到零錯誤的編碼方式。

Saphira · 2024-06-12 10:33:40

假設我們一次傳遞四個字（位）的信息

7個數字爲一組，十組就有70個數字，消失10%允許消失總計7個數字。如果每組各消失1個數字則能根據這個糾錯方法成功還原出正確的信息，那萬一消失的7個數字在同一組裏呢？這個數字組的信息就徹底丟失了。
~~我甚至不知道該數組是否存在過，更不用說還原出信息了~~

這個方法恐怕並不能保證連續的數字消失後依然可以還原，這就是我強調“任意消失10%”的原因。 [被炸]

最后修改： Saphira (2024-06-12 11:10:10)

安德Endur~ · 2024-06-12 17:19:10

提高通信系統可靠性的方法：增加冗餘碼 [被炸]
反正提高信道可靠性就得降低有效性了。
信號載波可以讓信息在消息量不變的情況下冗餘出一堆量出來，這堆量是可以隨意糟蹋但是放在碼裏的。控制信道誤碼率在百分之十，可以通過一些方法計算出需要的編碼方式。
特殊的編碼方式可以識別錯誤信息，有的也可以通過一些算法把原碼算出來，我記得QR好像遮住一部分還是能識別的。

[↑] @Saphira 寫道: 7個數字爲一組，十組就有70個數字，消失10%允許消失總計7個數字。如果每組各消失1個數字則能根據這個糾錯方法成功還原出正確的信息，那萬一消失的7個數字在同一組裏呢？這個數字組的信息就徹底丟失了。 …

誤碼率不是說每100碼裏就有10個是錯的，恢復成功率也不是百分百。

USB的串口也是普通的校驗手段，外接攝像頭以後傳輸出問題會一小排一小排出問題，UART也沒提供恢復數據的方案。
顯存出問題了一個畫面裏是每隔一段有一個小白塊塊，這時候會直接卡死，這是一整個儲存介質出問題了，假如這個龐大系統通過特殊爪段允許內存重排，GPU應該是能不用這個顯存來進行輸出的，只管後續buffer充出去就行。
一般常用的手段是哈希值校驗或者依據fft的校驗方法。
對傳統介質並且不能做高強度計算的生物來說，多複製幾份應該是比設計一套冗餘去冗餘編碼和解碼更簡單的——

最后修改：安德Endur~ (2024-06-12 17:35:57)

Lunamis午月 · 2024-06-12 19:48:08

[↑] @Amorphous 寫道: 當然是存在的！ 例如，我使用這樣的一種方法：鑑於用爪子在木材上寫字實際上是一件很麻煩的事情（木材的紋理走向導致各個方向的阻力不一致，沒法好好寫字），我只 …

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

shiningdracon · 2024-06-12 20:37:52

@Saphira 寫道: 這個方法恐怕並不能保證連續的數字消失後依然可以還原，這就是我強調“任意消失10%”的原因。

“任意”這個條件有點難處理。

我看到帖子的第一反應是冗餘存儲，第二反應是二維碼（二維碼帶冗餘糾錯）。但是它們不符合“任意”+ “百分比”。
有“百分比”這個條件，靠“多抄幾遍”就不行了。

第三想到的是全息攝影，把全息攝影的底片砸碎了，從每個碎片中都能還原出完整圖像（只是分辨率會下降）。但這個就不是“文字”了，還是不符合條件。

最后修改： shiningdracon (2024-06-12 21:13:39)

shiningdracon · 2024-06-12 21:07:19

這樣或許可以
用0123456789做原料拼成0123456789的字符畫，可以任意丟失10%的字符而不影響解讀

Saphira · 2024-06-12 21:23:16

用0123456789做原料拼成0123456789的字符畫，可以任意丟失10%的字符而不影響解讀

想了一下確實是好辦法，各部分能檢驗其他部分的完整性。
（小問題是每個數字佔的像素其實不一樣。簡單點說，雖然“十”和“龘”都是一個字，但是佔的屏幕顯示面積沒法比，“十龘”消失10%沒準能讓“十”變成“一”）
不知道能不能順着這個思路把“字”也加進來，而不僅僅侷限於數字

龍爪翻書 · 2024-06-12 21:55:33

前一陣子正好看到一張圖，好像就是刪除10%也能保留原始意思?

安德Endur~ · 2024-06-13 00:06:05

有“百分比”這個條件，靠“多抄幾遍”就不行了。

但多抄幾遍，所有的副本合起來作爲一個顯示的結果就可行了嘛，QR也能用這個方法。但是卷積確實是不符合條件的，所以得用fft了。

Saphira · 2024-06-13 00:31:50

但多抄幾遍，所有的副本合起來作爲一個顯示的結果就可行了嘛，QR也能用這個方法。

單個qr碼消失的10%恰好是版本信息就掃不出來了，多抄幾遍合起來會有一種可能：消失的10%全部集中於各qr碼的版本信息
這樣就都掃不出來了 [被炸]

Saphira · 2024-06-13 00:49:30

[↑] @龍爪翻書寫道: 前一陣子正好看到一張圖，好像就是刪除10%也能保留原始意思? …

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

Amorphous · 2024-06-13 03:06:44

[↑] @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。

Amorphous · 2024-06-13 03:38:10

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

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

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

Saphira · 2024-06-13 19:47:06

讓我們對文字按照位進行遞增編號

只有第2位信息爲1，於是我們忽略第0位

消失第一位後信息只剩下010，爲什麼在後續運算中默認消失的是第一位 (讓i=2) 而不是最後一位 (讓i=1)？
換句話說，當一隻龍看到剩餘的信息是010時，如何判斷原來的信息不是010x而是x010？

最后修改： Saphira (2024-06-13 19:57:49)

Amorphous · 2024-06-14 02:07:35

@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 2024-06-11 17:30:35 | 只看该作者