ในทฤษฎีสารสนเทศทฤษฎีการเข้ารหัสแหล่งข้อมูลของแชนนอน (หรือทฤษฎีการเข้ารหัสแบบไร้สัญญาณรบกวน ) กำหนดขีดจำกัดทางสถิติของการบีบอัดข้อมูล ที่เป็นไปได้ สำหรับข้อมูลที่มีแหล่งข้อมูลเป็นตัวแปรสุ่มอิสระที่มีการแจกแจงเหมือนกันและความหมายเชิงปฏิบัติการของเอนโทรปีของแชนนอน

ทฤษฎีการเข้ารหัสแหล่งข้อมูลซึ่งตั้งชื่อตามโคลด แชนนอนแสดงให้เห็นว่า ในขีดจำกัด เมื่อความยาวของกระแส ข้อมูล ตัวแปรสุ่มอิสระและมีการกระจายเหมือนกัน (iid)มีแนวโน้มเข้าสู่ค่าอนันต์ จะเป็นไปไม่ได้ที่จะบีบอัดข้อมูลดังกล่าวให้มีอัตราการเข้ารหัส (จำนวนบิตเฉลี่ยต่อสัญลักษณ์) น้อยกว่าเอนโทรปีของแชนนอนของแหล่งข้อมูล โดยที่ข้อมูลจะไม่สูญหายอย่างแน่นอน อย่างไรก็ตาม เป็นไปได้ที่จะได้อัตราการเข้ารหัสที่ใกล้เคียงกับเอนโทรปีของแชนนอนมากเท่าใดก็ได้ โดยมีความน่าจะเป็นที่จะสูญหายเพียงเล็กน้อย

ทฤษฎีการเข้ารหัสแหล่งที่มาสำหรับรหัสสัญลักษณ์กำหนดขอบเขตบนและขอบเขตล่างของความยาวขั้นต่ำที่เป็นไปได้ของคำรหัส โดยขึ้นอยู่กับเอนโทรปีของคำอินพุต (ซึ่งถือว่าเป็นตัวแปรสุ่ม ) และขนาดของตัวอักษรเป้าหมาย

โปรดทราบว่า สำหรับข้อมูลที่แสดงการพึ่งพาที่มากขึ้น (ซึ่งแหล่งที่มาไม่ใช่ตัวแปรสุ่มแบบ iid) ความซับซ้อนของ Kolmogorovซึ่งวัดความยาวคำอธิบายขั้นต่ำของวัตถุ จะเหมาะสมกว่าในการอธิบายขีดจำกัดของการบีบอัดข้อมูล เอนโทรปีของ Shannon พิจารณาเฉพาะความสม่ำเสมอของความถี่ ในขณะที่ความซับซ้อนของ Kolmogorov พิจารณาความสม่ำเสมอของอัลกอริทึมทั้งหมด ดังนั้นโดยทั่วไปแล้วค่าหลังจะน้อยกว่า ในทางกลับกัน หากวัตถุถูกสร้างขึ้นโดยกระบวนการสุ่มในลักษณะที่มีเฉพาะความสม่ำเสมอของความถี่ เอนโทรปีจะใกล้เคียงกับความซับซ้อนด้วยความน่าจะเป็นสูง (Shen et al. 2017) ^{[ 1 ]}

การเข้ารหัสแหล่งข้อมูล ( Source coding ) คือการแปลงสัญลักษณ์ (ลำดับของสัญลักษณ์) จากแหล่ง ข้อมูล ไปเป็นลำดับของสัญลักษณ์ตัวอักษร (โดยปกติคือบิต) โดยที่สัญลักษณ์จากแหล่งข้อมูลสามารถกู้คืนได้อย่างแม่นยำจากสัญลักษณ์ตัวอักษร (การเข้ารหัสแหล่งข้อมูลแบบไม่สูญเสีย) หรือกู้คืนได้โดยมีการบิดเบือนบ้าง (การเข้ารหัสแหล่งข้อมูลแบบสูญเสีย) นี่เป็นแนวทางหนึ่งในการบีบ อัดข้อมูล

ในทฤษฎีสารสนเทศ ทฤษฎีบทการเข้ารหัสแหล่งที่มา (Shannon 1948) ^{[ 2 ]}ระบุอย่างไม่เป็นทางการว่า (MacKay 2003, หน้า 81, ^{[ 3 ]} Cover 2006, บทที่ 5 ^{[ 4 ]} ):

ตัวแปรสุ่ม อิสระ และมีการกระจายเหมือนกันจำนวน Nตัว แต่ละตัวมีเอนโทรปีH ( X )สามารถบีบอัดให้เหลือมากกว่าNH ( X ) บิตได้โดยมีความเสี่ยงต่อการสูญเสียข้อมูลน้อยมาก เมื่อN → ∞แต่ในทางกลับกัน หากบีบอัดให้เหลือน้อยกว่าNH ( X )บิต ความเสี่ยงต่อการสูญเสียข้อมูลแทบจะแน่นอน

ลำดับรหัสที่มีความยาวดังกล่าวแสดงถึงข้อความที่ถูกบีบอัดในลักษณะสองทาง โดยอยู่บนสมมติฐานว่าผู้ถอดรหัสรู้แหล่งที่มา ในทางปฏิบัติ สมมติฐานนี้ไม่เป็นจริงเสมอไป ดังนั้น เมื่อใช้การเข้ารหัสแบบเอนโทรปี ข้อความที่ส่งอาจจำเป็นต้องมีข้อมูลที่บ่งบอกลักษณะของแหล่งที่มา ซึ่งโดยปกติจะแทรกไว้ที่จุดเริ่มต้นของข้อความที่ส่ง ${\displaystyle NH(X)}$

ให้Σ ₁ , Σ ₂แทนตัวอักษรจำกัดสองตัว และให้Σ^* ₁และΣ^* ₂หมายถึงเซตของคำจำกัดทั้งหมดจากตัวอักษรเหล่านั้น (ตามลำดับ)

สมมติว่าXเป็นตัวแปรสุ่มที่รับค่าในΣ ₁และให้fเป็น รหัส ที่ถอดรหัสได้เพียงหนึ่งเดียวจากΣ^* ₁ถึงΣ^* ₂โดย ที่|Σ ₂ | = aให้Sแทนตัวแปรสุ่มที่กำหนดโดยความยาวของรหัสคำf ( X )

ถ้าfเป็นฟังก์ชันที่เหมาะสมที่สุดในแง่ที่ว่ามีความยาวคำที่คาดหวังน้อยที่สุดสำหรับXแล้ว (แชนนอน 1948):

${\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} [S]<{\frac {H(X)}{\log _{2}a}}+1}$

โดยที่หมายถึงตัวดำเนินการ ค่าคาดหวัง${\displaystyle \mathbb {E} }$

กำหนดให้Xเป็นแหล่งข้อมูลอิสระและ มีการแจกแจง เหมือนกัน (iid ) อนุกรมเวลาX ₁ , ..., X _n ของมัน ก็มีการ แจกแจงเหมือนกันและมีการแจกแจงเหมือนกัน (iid) โดยมีเอนโทรปี H ( X )ในกรณีค่าไม่ต่อเนื่อง และเอนโทรปีเชิงอนุพันธ์ ในกรณี ค่าต่อเนื่อง ทฤษฎีบทการเข้ารหัสแหล่งข้อมูลระบุว่า สำหรับε > 0 ใดๆ กล่าว คือ สำหรับอัตราH ( X ) + ε ใดๆ ที่มากกว่าเอนโทรปี ของแหล่งข้อมูล จะมีค่า nที่มากพอและมีตัวเข้ารหัสที่รับการทำซ้ำแหล่งข้อมูลX ^{1: n} จำนวน n ครั้งแบบ iid และแปลงเป็น บิตไบนารี n ( H ( X ) + ε )บิต โดยที่สัญลักษณ์แหล่งข้อมูลX ^{1: n}สามารถกู้คืนได้จากบิตไบนารีด้วยความน่าจะเป็นอย่างน้อย1 − ε

การพิสูจน์ความเป็นไปได้ กำหนดค่า ε > 0บางค่าและให้

${\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].}$

ชุดทั่วไป , A^ε _nซึ่งกำหนดไว้ดังนี้:

${\displaystyle A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}.}$

คุณสมบัติการแบ่งส่วนเท่าๆ กันแบบเชิงอะซิมโทติก ( AEP) แสดงให้เห็นว่า สำหรับค่า nที่มากพอความน่าจะเป็นที่ลำดับที่สร้างขึ้นโดยแหล่งกำเนิดจะอยู่ในเซตทั่วไปA^ε _nตามที่กำหนดไว้ ค่าจะเข้าใกล้หนึ่ง โดยเฉพาะอย่างยิ่ง สำหรับค่า n ที่มากพอ ค่าสามารถทำให้เข้าใกล้ 1 ได้อย่างไม่จำกัด และโดยเฉพาะอย่างยิ่ง มากกว่า(ดู AEPสำหรับหลักฐาน) ${\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}$${\displaystyle 1-\varepsilon }$

นิยามของเซตทั่วไปบ่งชี้ว่าลำดับที่อยู่ในเซตทั่วไปนั้นต้องเป็นไปตามเงื่อนไขต่อไปนี้:

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}}$

• ความน่าจะเป็นที่ลำดับจะถูกสุ่มมาจากA${\displaystyle (X_{1},X_{2},\cdots X_{n})}$^ε _nมีค่ามากกว่า1 − ε
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}$ซึ่งเป็นผลมาจากด้านซ้ายมือ (ขอบล่าง) สำหรับ${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}$ซึ่งเป็นผลมาจากขอบเขตบนสำหรับ และขอบเขตล่างของความน่าจะเป็นทั้งหมดของเซตA ทั้งหมด${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$^ε _n.

เนื่องจากบิตเพียงพอที่จะชี้ไปยังสตริงใดๆ ในเซตนี้ได้ ${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n(H(X)+\varepsilon )}$

อัลกอริทึมการเข้ารหัส: ตัวเข้ารหัสจะตรวจสอบว่าลำดับอินพุตอยู่ในเซตทั่วไปหรือไม่ ถ้าใช่ จะส่งออกดัชนีของลำดับอินพุตภายในเซตทั่วไป ถ้าไม่ ตัวเข้ารหัสจะส่งออกตัวเลขn ( H ( X ) + ε )หลักแบบสุ่ม ตราบใดที่ลำดับอินพุตอยู่ในเซตทั่วไป (ด้วยความน่าจะเป็นอย่างน้อย1 − ε ) ตัวเข้ารหัสจะไม่เกิดข้อผิดพลาด ดังนั้น ความน่าจะเป็นของข้อผิดพลาดของตัวเข้ารหัสจึงมีค่าสูงสุดไม่เกิน ε

การพิสูจน์บทกลับ : บทกลับได้รับการพิสูจน์โดยการแสดงว่าเซตใดๆ ที่มีขนาดเล็กกว่าA^ε _n(ในแง่ของเลขชี้กำลัง) จะครอบคลุมเซตของความน่าจะเป็นที่อยู่ห่างจาก1อย่าง มีขอบเขต

สำหรับ1 ≤ i ≤ nให้s _iแทนความยาวของคำแต่ละคำของx _i ที่เป็นไปได้ กำหนดโดยที่Cถูกเลือกเพื่อให้q ₁ + ... + q _n = 1จากนั้น ${\displaystyle q_{i}=a^{-s_{i}}/C}$

${\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}}$

โดยบรรทัดที่สองได้มาจากอสมการของ Gibbsและบรรทัดที่ห้าได้มาจากอสมการของ Kraft :

${\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}$

ดังนั้นlog C ≤ 0

สำหรับอสมการที่สอง เราอาจกำหนดได้ว่า

${\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }$

ดังนั้น

${\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}$

และดังนั้น

${\displaystyle a^{-s_{i}}\leq p_{i}}$

และ

${\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}$

ดังนั้นโดยอสมการของคราฟต์ จึงมีรหัสที่ไม่มีคำนำหน้าซึ่งมีความยาวคำเหล่านั้น ดังนั้นS ที่เล็กที่สุดจึง เป็นไปตามเงื่อนไข นี้

${\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}$

กำหนดเซตทั่วไปA^ε _nเช่น:

${\displaystyle A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}.}$

จากนั้น สำหรับδ > 0 ที่กำหนด สำหรับnที่มากพอPr( A^ε _n) > 1 − δตอนนี้เราเพียงแค่เข้ารหัสลำดับในเซตทั่วไป และวิธีการปกติในการเข้ารหัสแหล่งที่มาแสดงให้เห็นว่าจำนวนสมาชิกของเซตนี้น้อยกว่าดังนั้นโดยเฉลี่ยแล้ว บิต H _n ( X ) + εก็เพียงพอสำหรับการเข้ารหัสด้วยความน่าจะเป็นที่มากกว่า1 − δโดยที่εและδสามารถทำให้มีค่าน้อยลงได้ตามอำเภอใจ โดยการทำให้nมีค่ามากขึ้น ${\displaystyle 2^{n({\overline {H_{n}}}(X)+\varepsilon )}}$

• การเข้ารหัสช่องสัญญาณ
• เลขชี้กำลังข้อผิดพลาด
• ทฤษฎีการเข้ารหัสช่องสัญญาณรบกวน