รหัสขยาย
กราฟขยายแบบสองส่วน
การจำแนกประเภท
พิมพ์	รหัสบล็อกเชิงเส้น
ความยาวบล็อก	${\displaystyle n}$
ความยาวของข้อความ	${\displaystyle nm}$
ประเมิน	${\displaystyle 1-m/n}$
ระยะทาง	${\displaystyle 2(1-\epsilon )\gamma \cdot n}$
ขนาดตัวอักษร	${\displaystyle 2}$
สัญกรณ์	${\displaystyle [n,nm,2(1-\epsilon )\gamma \cdot n]_{2}}$-รหัส
วี ที อี

ในทฤษฎีการเข้ารหัสรหัสขยาย (expander codes)จัดอยู่ในกลุ่มรหัสแก้ไขข้อผิดพลาดที่สร้างขึ้นจากกราฟขยาย แบบสอง ส่วน (bipartite expander graphs) รหัสขยายมีความน่าสนใจเป็นพิเศษเช่นเดียวกับรหัสจัสเตเซน (Justesen codes ) เนื่องจากมี อัตรา บวกคงที่ ระยะทางสัมพัทธ์บวกคงที่และขนาดตัวอักษร คงที่ ที่จริงแล้ว ตัวอักษรมีเพียงสององค์ประกอบ ดังนั้นรหัสขยายจึงจัดอยู่ในกลุ่มรหัสไบนารียิ่งไปกว่านั้น รหัสขยายสามารถเข้ารหัสและถอดรหัสได้ในเวลาที่แปรผันตามความยาวบล็อกของรหัส

ในทฤษฎีการเข้ารหัสรหัสขยาย (expander code) คือรหัสบล็อกเชิงเส้นที่มีเมทริกซ์ตรวจสอบความเท่าเทียมกัน (parity check matrix) เป็นเมทริกซ์ประชิด (adjacency matrix)ของกราฟขยาย แบบสองส่วน (bipartite expander graph) รหัสเหล่านี้มีระยะ ห่างสัมพัทธ์ที่ดี โดยที่และเป็นคุณสมบัติของกราฟขยายตามที่กำหนดไว้ในภายหลังมีอัตราและความสามารถในการถอดรหัส (มีอัลกอริธึมที่มีประสิทธิภาพในเวลาการทำงาน) ${\displaystyle [n,nm]_{2}\,}$${\displaystyle 2(1-\varepsilon )\gamma \,}$${\displaystyle \varepsilon \,}$${\displaystyle \gamma \,}$${\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}$${\displaystyle O(n)\,}$

ให้เป็นกราฟไบเรกูลาร์ระหว่างเซตของโหนดที่เรียกว่าตัวแปรและเซตของโหนดที่เรียกว่าข้อจำกัด ${\displaystyle B}$${\displaystyle (c,d)}$${\displaystyle n}$${\displaystyle \{v_{1},\cdots ,v_{n}\}}$${\displaystyle cn/d}$${\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}$

ให้เป็นฟังก์ชันที่ออกแบบมาเพื่อให้สำหรับแต่ละข้อจำกัดตัวแปรที่อยู่ใกล้เคียงกัน คือ${\displaystyle b(i,j)}$${\displaystyle C_{i}}$${\displaystyle C_{i}}$${\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}$

ให้เป็นรหัสแก้ไขข้อผิดพลาดที่มีความยาวบล็อกรหัสขยายคือ รหัสที่มีความยาวบล็อกซึ่งคำรหัส คือ คำที่สำหรับเป็นคำรหัสของ^{[ 1 ]}${\displaystyle {\mathcal {S}}}$${\displaystyle d}$${\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}$${\displaystyle n}$${\displaystyle (x_{1},\cdots ,x_{n})}$${\displaystyle 1\leq i\leq cn/d}$${\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}$${\displaystyle {\mathcal {S}}}$

ได้มีการแสดงให้เห็นแล้วว่ากราฟขยายแบบไม่สูญเสียที่ไม่ใช่แบบธรรมดามีอยู่จริง ยิ่งไปกว่านั้น เราสามารถสร้างกราฟเหล่านั้นได้อย่างชัดเจน^{[ 2 ]}

อัตราของเมทริกซ์ตรวจสอบความเท่าเทียมกันคือขนาดของเมทริกซ์หารด้วยความยาวของบล็อก ในกรณีนี้ เมทริกซ์ตรวจสอบความเท่าเทียมกันมีขนาดเท่ากับและดังนั้นจึงมีอัตราอย่างน้อยเท่ากับ ${\displaystyle C\,}$${\displaystyle m\times n\,}$${\displaystyle C\,}$${\displaystyle (nm)/n=1-m/n\,}$

สมมติว่าดังนั้นระยะทางของรหัสขยายจะมีค่าอย่างน้อยที่สุด ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$${\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}$${\displaystyle C\,}$${\displaystyle 2(1-\varepsilon )\gamma n\,}$

โปรดทราบว่าเราสามารถพิจารณาคำรหัสทุกคำในเป็นเซตย่อยของจุดยอดโดยกล่าวว่าจุดยอดนั้นเป็นจุดรหัสก็ต่อเมื่อดัชนีที่ ของคำรหัสเป็น 1 เท่านั้น ดังนั้นจะเป็นคำรหัสก็ต่อเมื่อจุดยอดทุกจุดใน อยู่ติดกับจุดยอดจำนวนคู่ใน(เพื่อให้ เป็นคำรหัสโดยที่คือเมทริกซ์ตรวจสอบความเท่าเทียมกัน ดังนั้น จุดยอดแต่ละจุดในจะสอดคล้องกับแต่ละคอลัมน์ของการ คูณเมทริกซ์เหนือจะให้ผลลัพธ์ที่ต้องการ) ดังนั้น ถ้าจุดยอดอยู่ติดกับจุดยอดเพียงจุดเดียวในเราจะรู้ได้ทันทีว่าไม่ใช่คำรหัส ให้แทนจุดยอดข้างเคียงในของและแทนจุดยอดข้างเคียงของซึ่งมีเอกลักษณ์เฉพาะตัว กล่าวคือ อยู่ติดกับจุดยอดเพียงจุดเดียวของ ${\displaystyle c\,}$${\displaystyle C\,}$${\displaystyle S\subset L\,}$${\displaystyle v_{i}\in S\,}$${\displaystyle i\,}$${\displaystyle c\,}$${\displaystyle v\in R\,}$${\displaystyle S\,}$${\displaystyle cP=0\,}$${\displaystyle P\,}$${\displaystyle R\,}$${\displaystyle P\,}$${\displaystyle {\text{GF}}(2)=\{0,1\}\,}$${\displaystyle v\in R\,}$${\displaystyle S\,}$${\displaystyle c\,}$${\displaystyle N(S)\,}$${\displaystyle R\,}$${\displaystyle S\,}$${\displaystyle U(S)\,}$${\displaystyle S\,}$${\displaystyle S\,}$

สำหรับทุก ขนาด.${\displaystyle S\subset L\,}$${\displaystyle |S|\leq \gamma n\,}$${\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}$

โดยทั่วไปแล้วเนื่องจากหมายความว่าเป็น ไปตามนั้น เนื่องจากดีกรีของทุกจุดยอดในคือโดยคุณสมบัติการขยายของกราฟ จะต้องมีเซตของขอบที่เชื่อมไปยังจุดยอดที่แตกต่างกันขอบที่เหลือทำให้มีเพื่อนบ้านอย่างมากที่สุดเพื่อนบ้านที่ไม่ซ้ำกันดังนั้น ${\displaystyle |N(S)|\geq |U(S)|\,}$${\displaystyle v\in U(S)\,}$${\displaystyle v\in N(S)\,}$${\displaystyle |N(S)|\leq d|S|\,}$${\displaystyle S\,}$${\displaystyle d\,}$${\displaystyle d(1-\varepsilon )|S|\,}$${\displaystyle d\varepsilon |S|\,}$${\displaystyle d\varepsilon |S|\,}$${\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}$

ทุก ๆ จุดที่เล็กพอจะมีเพื่อนบ้านที่ไม่ซ้ำกัน นี่เป็นผลมาจาก... ${\displaystyle S\,}$${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$

เซต ย่อยทุกเซตจะมีเพื่อนบ้านที่ไม่ซ้ำกัน ${\displaystyle T\subset L\,}$${\displaystyle |T|<2(1-\varepsilon )\gamma n\,}$

บทพิสูจน์เสริมที่ 1 พิสูจน์กรณีดังนั้นสมมติว่าให้ โดย ที่โดยบทพิสูจน์เสริมที่ 1 เราทราบว่าดังนั้นจุดยอดอยู่ในถ้าและเรารู้ว่าดังนั้นโดยส่วนแรกของบทพิสูจน์เสริมที่ 1 เราทราบว่าเนื่องจากและดังนั้น จึงไม่ว่างเปล่า ${\displaystyle |T|\leq \gamma n\,}$${\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}$${\displaystyle S\subset T\,}$${\displaystyle |S|=\แกมมา n\,}$${\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}$${\displaystyle v\in U(S)\,}$${\displaystyle U(T)\,}$${\displaystyle v\notin N(T\setminus S)\,}$${\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}$${\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}$${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$${\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}$${\displaystyle U(T)\,}$

โปรดทราบว่า ถ้า a มีเพื่อนบ้านที่ไม่ซ้ำกันอย่างน้อย 1 ตัว เช่นแล้วคำที่สอดคล้องกับจะไม่ใช่คำรหัส เนื่องจากจะไม่สามารถคูณกับเมทริกซ์ตรวจสอบความเท่าเทียมกันแล้วได้เวกเตอร์ที่เป็นศูนย์ทั้งหมด จากข้อโต้แย้งก่อนหน้านี้ เนื่องจากเป็นเชิงเส้น เราจึงสรุปได้ว่ามีระยะห่างอย่างน้อย ${\displaystyle T\subset L\,}$${\displaystyle |U(T)|>0\,}$${\displaystyle c\,}$${\displaystyle T\,}$${\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}$${\displaystyle C\,}$${\displaystyle C\,}$${\displaystyle 2(1-\varepsilon )\gamma n\,}$

เวลาการเข้ารหัสสำหรับรหัสขยายจะถูกจำกัดสูงสุดโดยรหัสเชิงเส้น ทั่วไป - โดยการคูณเมทริกซ์ ผลลัพธ์ของ Spielman แสดงให้เห็นว่าการเข้ารหัสสามารถทำได้ในเวลา^{[ 3 ]}${\displaystyle O(n^{2})\,}$${\displaystyle O(n)\,}$

การถอดรหัสขยายรหัสสามารถทำได้ทันเวลาเมื่อใช้อัลกอริทึมต่อไปนี้ ${\displaystyle O(n)\,}$${\displaystyle \varepsilon <{\tfrac {1}{4}}\,}$

ให้เป็นจุดยอดของที่สอดคล้องกับดัชนีในคำรหัสของให้เป็นคำที่ได้รับ และให้เป็นและเป็น จากนั้นพิจารณาอัลกอริทึมแบบโลภ (greedy algorithm) ดังนี้ : ${\displaystyle v_{i}\,}$${\displaystyle L\,}$${\displaystyle i\,}$${\displaystyle C\,}$${\displaystyle y\in \{0,1\}^{n}\,}$${\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}$${\displaystyle e(i)\,}$${\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,}$${\displaystyle o(i)\,}$${\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,}$

อินพุต:คำที่ได้รับ ${\displaystyle y\,}$

กำหนดค่าเริ่มต้น y' เป็น y ในขณะที่มี av ใน R ที่อยู่ติดกับจำนวนจุดยอดคี่ใน V(y') ถ้ามีค่า i ที่ทำให้ o(i) > e(i) พลิกรายการ i ใน y' อื่น ล้มเหลว 

ผลลัพธ์:ล้มเหลว หรือรหัสคำที่ถูกแก้ไข ${\displaystyle y'\,}$

เราจะแสดงให้เห็นถึงความถูกต้องของอัลกอริทึมก่อน จากนั้นจึงตรวจสอบเวลาในการทำงานของอัลกอริทึม

เราต้องแสดงให้เห็นว่าอัลกอริทึมจะสิ้นสุดลงด้วยรหัสคำที่ถูกต้องเมื่อรหัสคำที่ได้รับอยู่ภายในครึ่งหนึ่งของระยะห่างของรหัสจากรหัสคำเดิม ให้เซตของตัวแปรที่เสียหายเป็น, , และเซตของจุดยอดที่ไม่ตรงตามเงื่อนไข (อยู่ติดกับจุดยอดจำนวนคี่) ในเป็นบทพิสูจน์ต่อไปนี้จะเป็นประโยชน์ ${\displaystyle S\,}$${\displaystyle s=|S|\,}$${\displaystyle R\,}$${\displaystyle c\,}$

ถ้า เช่นนั้น จะ มีค่า อยู่ด้วย${\displaystyle 0<s<\gamma n\,}$${\displaystyle v_{i}\,}$${\displaystyle o(i)>e(i)\,}$

จาก Lemma 1 เราทราบว่าดังนั้นจุดยอดเฉลี่ยจะมีเพื่อนบ้านที่ไม่ซ้ำกันอย่างน้อย(จำไว้ว่าเพื่อนบ้านที่ไม่ซ้ำกันจะไม่พึงพอใจและจึงมีส่วนร่วมใน) เนื่องจากและด้วยเหตุนี้จึงมีจุดยอดที่มี ${\displaystyle U(S)\geq d(1-2\varepsilon )s\,}$${\displaystyle d(1-2\varepsilon )>d/2\,}$${\displaystyle o(i)\,}$${\displaystyle \varepsilon <{\tfrac {1}{4}}\,}$${\displaystyle v_{i}\,}$${\displaystyle o(i)>e(i)\,}$

ดังนั้น หากเรายังไม่ถึงรหัสคำ ก็จะมีจุดยอดบางจุดที่ต้องพลิกเสมอ ต่อไป เราจะแสดงให้เห็นว่าจำนวนข้อผิดพลาดไม่สามารถเพิ่มขึ้นเกินกว่าได้ ${\displaystyle \gamma n\,}$

ถ้าเราเริ่มต้นด้วยค่านี้เราจะไม่มีวันไปถึงจุดใด ๆ ในอัลกอริธึมเลย ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$${\displaystyle s=\gamma n\,}$

เมื่อเราพลิกจุดยอดและสลับตำแหน่งกัน และเนื่องจากเรามีนั่นหมายความว่าจำนวนจุดยอดที่ไม่สมบูรณ์ทางด้านขวาจะลดลงอย่างน้อยหนึ่งจุดหลังจากการพลิกแต่ละครั้ง เนื่องจากจำนวนจุดยอดที่ไม่สมบูรณ์เริ่มต้นจึงมีค่าสูงสุดตาม ความสม่ำเสมอ ของกราฟหากเราพบสตริงที่มีข้อผิดพลาด ตาม Lemma 1 จะมีเพื่อนบ้านที่ไม่ซ้ำกันอย่างน้อย ซึ่งหมายความว่าจะมีจุดยอดที่ไม่สมบูรณ์อย่างน้อย ซึ่งขัดแย้งกัน ${\displaystyle v_{i}\,}$${\displaystyle o(i)\,}$${\displaystyle e(i)\,}$${\displaystyle o(i)>e(i)\,}$${\displaystyle s<\gamma (1-2\varepsilon )n\,}$${\displaystyle d\gamma (1-2\varepsilon )n\,}$${\displaystyle d\,}$${\displaystyle \gamma n\,}$${\displaystyle d\gamma (1-2\varepsilon )n\,}$${\displaystyle d\gamma (1-2\varepsilon )n\,}$

บทพิสูจน์เสริมข้อที่ 3 และ 4 แสดงให้เราเห็นว่า ถ้าเราเริ่มต้นด้วย(ครึ่งหนึ่งของระยะทางของ) เราจะพบจุดยอดที่จะพลิกเสมอ การพลิกแต่ละครั้งจะลดจำนวนจุดยอดที่ไม่ตรงตามเงื่อนไขใน ลงอย่างน้อย 1 จุด ดังนั้นอัลกอริทึมจึงสิ้นสุดลงในขั้นตอนอย่างมากที่สุด และจะสิ้นสุดที่คำรหัสบางคำ ตามบทพิสูจน์เสริมข้อที่ 3 (หากไม่สิ้นสุดที่คำรหัส ก็จะมีจุดยอดให้พลิกอีกจุดหนึ่ง) บทพิสูจน์เสริมข้อที่ 4 แสดงให้เราเห็นว่าเราไม่สามารถอยู่ห่างจากคำรหัสที่ถูกต้องได้มากกว่า เนื่องจากรหัสมีระยะทาง(เนื่องจาก) คำรหัสที่สิ้นสุดลงจึงต้องเป็นคำรหัสที่ถูกต้อง เนื่องจากจำนวนการพลิกบิตน้อยกว่าครึ่งหนึ่งของระยะทาง (ดังนั้นเราจึงไม่สามารถเดินทางไปไกลพอที่จะไปถึงคำรหัสอื่นได้) ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$${\displaystyle C\,}$${\displaystyle v_{i}\,}$${\displaystyle R\,}$${\displaystyle m\,}$${\displaystyle \gamma n\,}$${\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}$${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$

ต่อไปนี้เราจะแสดงให้เห็นว่าอัลกอริธึมนี้สามารถถอดรหัสได้ในเวลาเชิงเส้น ให้เป็นค่าคงที่ และให้เป็นดีกรีสูงสุดของจุดยอดใดๆ ในโปรดทราบว่าก็เป็นค่าคงที่เช่นกันสำหรับโครงสร้างที่ทราบแล้ว ${\displaystyle {\tfrac {n}{m}}\,}$${\displaystyle r\,}$${\displaystyle R\,}$${\displaystyle r\,}$

1. ขั้นตอนการประมวลผลเบื้องต้น: การคำนวณว่าแต่ละจุดยอดมีจำนวนเพื่อนบ้านเป็นเลขคี่หรือเลขคู่ ต้องใช้เวลา${\displaystyle O(mr)\,}$${\displaystyle R\,}$
2. ขั้นตอนการประมวลผลเบื้องต้น 2: เราใช้เวลาในการคำนวณรายการจุดยอดที่มี.${\displaystyle O(dn)=O(dmr)\,}$${\displaystyle v_{i}\,}$${\displaystyle L\,}$${\displaystyle o(i)>e(i)\,}$
3. ในแต่ละรอบการทำงาน: เราเพียงแค่ลบองค์ประกอบแรกในรายการออก เพื่ออัปเดตรายการของจุดยอดคี่/คู่ในเราจำเป็นต้องอัปเดตเฉพาะรายการ โดยแทรก/ลบตามความจำเป็น จากนั้นเราจะอัปเดตรายการในรายการจุดยอดในที่มีเพื่อนบ้านเป็นเลขคี่มากกว่าเลขคู่ โดยแทรก/ลบตามความจำเป็น ดังนั้นแต่ละรอบการทำงานจึงใช้เวลา${\displaystyle R\,}$${\displaystyle O(d)\,}$${\displaystyle O(dr)\,}$${\displaystyle L\,}$${\displaystyle O(dr)\,}$
4. ตามที่ได้กล่าวไว้ข้างต้น จำนวนรอบการทำซ้ำทั้งหมดมีค่าสูงสุดไม่เกิน.${\displaystyle m\,}$

ซึ่งจะทำให้ได้เวลาการทำงานทั้งหมดเท่ากับเวลา โดยที่และเป็นค่าคงที่ ${\displaystyle O(mdr)=O(n)\,}$${\displaystyle d\,}$${\displaystyle r\,}$

• กราฟขยาย
• รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ
• การเข้ารหัสและการถอดรหัสแบบเชิงเส้นตามเวลาของรหัสแก้ไขข้อผิดพลาด
• รหัส ABNNR และ AEL

บทความนี้อ้างอิงจากบันทึกหลักสูตรของ ดร. เวนกาเตสัน กูรุสวามี^{[ 4 ]}