ในทฤษฎีการเข้ารหัสรหัสเชิงเส้นเป็นรหัสแก้ไขข้อผิดพลาดซึ่งการรวมกันเชิงเส้น ใดๆ ของคำรหัสก็ถือเป็นคำรหัสเช่นกัน รหัสเชิงเส้นโดยทั่วไปจะแบ่งออกเป็นรหัสบล็อกและรหัสคอนโวลูชันแม้ว่ารหัสเทอร์โบจะถือได้ว่าเป็นลูกผสมของทั้งสองประเภทนี้ ก็ตาม ^{[ 1 ]}รหัสเชิงเส้นช่วยให้สามารถใช้อัลกอริธึมการเข้ารหัสและการถอดรหัสที่มีประสิทธิภาพมากกว่ารหัสอื่นๆ (เช่นการถอดรหัสซินโดรม )

รหัสเชิงเส้นถูกใช้ในการแก้ไขข้อผิดพลาดล่วงหน้าและนำไปใช้ในวิธีการส่งสัญลักษณ์ (เช่นบิต ) บนช่องทางการสื่อสารเพื่อให้หากเกิดข้อผิดพลาดในการสื่อสาร ผู้รับบล็อกข้อความสามารถแก้ไขหรือตรวจจับข้อผิดพลาดบางอย่างได้ รหัสคำในรหัสบล็อกเชิงเส้นคือบล็อกของสัญลักษณ์ที่เข้ารหัสโดยใช้สัญลักษณ์มากกว่าค่าเดิมที่จะส่ง^{[ 2 ]} รหัสเชิงเส้นที่มีความยาวnจะส่งบล็อกที่มี สัญลักษณ์ nตัว ตัวอย่างเช่นรหัสแฮมมิ ง [7,4,3] เป็นรหัสไบนารี เชิงเส้น ที่แสดงข้อความ 4 บิตโดยใช้รหัสคำ 7 บิต รหัสคำสองรหัสที่แตกต่างกันอย่างน้อยสามบิต ผลที่ตามมาคือสามารถตรวจจับข้อผิดพลาดได้สูงสุดสองข้อต่อรหัสคำ ในขณะที่สามารถแก้ไขข้อผิดพลาดได้เพียงข้อเดียว^{[ 3 ]} รหัสนี้ประกอบด้วย 2 ⁴  = 16 รหัสคำ

รหัสเชิงเส้นที่มีความยาวnและมิติkคือปริภูมิย่อยเชิงเส้นCที่มีมิติkของปริภูมิเวกเตอร์ โดยที่เป็นฟิลด์จำกัดที่มี สมาชิก qตัว รหัสดังกล่าวเรียกว่า รหัส q -ary ถ้าq  = 2 หรือq  = 3 รหัสจะถูกอธิบายว่าเป็นรหัสไบนารีหรือรหัสเทอร์นารีตามลำดับ เวกเตอร์ในCเรียกว่าคำรหัสขนาดของรหัสคือจำนวนคำรหัสและเท่ากับ q ^k${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle \mathbb {F} _{q}}$

น้ำหนักของรหัสคำคือจำนวนองค์ประกอบที่ไม่เป็นศูนย์ และระยะห่างระหว่างรหัสคำสองรหัสคือระยะทางแฮมมิง (Hamming distance) ซึ่งก็คือจำนวนองค์ประกอบที่แตกต่างกัน ระยะทางdของรหัสเชิงเส้นคือน้ำหนักต่ำสุดของรหัสคำที่ไม่เป็นศูนย์ หรือเทียบเท่ากับระยะทางต่ำสุดระหว่างรหัสคำที่แตกต่างกัน รหัสเชิงเส้นที่มีความยาวnมิติkและระยะทางdเรียกว่ารหัส [ n , k , d ] (หรือเรียกให้ถูกต้องกว่านั้นคือรหัส) ${\displaystyle [n,k,d]_{q}}$

เราต้องการกำหนดฐานมาตรฐานเนื่องจากพิกัดแต่ละตัวแทน "บิต" ที่ส่งผ่าน "ช่องสัญญาณที่มีสัญญาณรบกวน" โดยมีความน่าจะเป็นเล็กน้อยของข้อผิดพลาดในการส่ง ( ช่องสัญญาณสมมาตรแบบไบนารี ) หากใช้ฐานอื่น โมเดลนี้จะไม่สามารถใช้งานได้ และเมตริกแฮมมิงจะไม่สามารถวัดจำนวนข้อผิดพลาดในการส่งได้ตามที่เราต้องการ ${\displaystyle \mathbb {F} _{q}^{n}}$

เนื่องจากเป็นปริภูมิย่อยเชิงเส้นของรหัสทั้งหมดC (ซึ่งอาจมีขนาดใหญ่มาก) สามารถแทนได้ด้วยการแผ่ขยายของชุดคำรหัส (ที่เรียกว่าฐานในพีชคณิตเชิงเส้น ) คำรหัสฐานเหล่านี้มักจะถูกจัดเรียงในแถวของเมทริกซ์ G ที่เรียกว่าเมทริกซ์ก่อกำเนิดสำหรับรหัสCเมื่อ G มีรูปแบบเมทริกซ์บล็อกโดยที่แทนเมทริกซ์เอกลักษณ์และ P เป็นเมทริกซ์บางตัว เราจะกล่าวว่า G อยู่ในรูปแบบมาตรฐาน ${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle k}$${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$${\displaystyle I_{k}}$${\displaystyle k\times k}$${\displaystyle k\times (nk)}$

เมทริกซ์Hที่แทนฟังก์ชันเชิงเส้นซึ่ง มี เคอร์เนลเป็นCเรียกว่าเมทริกซ์ตรวจสอบของC (หรือบางครั้งเรียกว่าเมทริกซ์ตรวจสอบความเท่าเทียมกัน) หรืออีกนัยหนึ่งHคือเมทริกซ์ที่มีปริภูมิว่างเป็นCถ้าCเป็นรหัสที่มีเมทริกซ์กำเนิดGในรูปแบบมาตรฐานแล้วคือเมทริกซ์ตรวจสอบสำหรับ C รหัสที่สร้างโดยHเรียกว่ารหัสคู่ของ C สามารถตรวจสอบได้ว่า G เป็นเมทริกซ์ ในขณะที่ H เป็นเมทริกซ์ ${\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{nk}}$${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$${\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{nk}]}$${\displaystyle k\times n}$${\displaystyle (nk)\times n}$

ความเป็นเชิงเส้นรับประกันว่าระยะทางแฮมมิง ขั้นต่ำ dระหว่างคำรหัสc ₀และคำรหัสอื่นๆc  ≠  c ₀จะไม่ขึ้นอยู่กับc ₀ซึ่งเป็นผลมาจากคุณสมบัติที่ว่าผลต่างc  −  c ₀ของคำรหัสสองคำในCก็เป็นคำรหัสเช่นกัน (กล่าวคือ เป็นสมาชิกของปริภูมิย่อยC ) และคุณสมบัติที่ว่าd ( c , c ₀ ) =  d ( c  −  c ₀ , 0) คุณสมบัติเหล่านี้บ่งชี้ว่า

${\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}$

กล่าวอีกนัยหนึ่ง ในการหาค่าระยะห่างน้อยที่สุดระหว่างรหัสคำของรหัสเชิงเส้น เราเพียงแค่ต้องพิจารณารหัสคำที่ไม่เป็นศูนย์เท่านั้น รหัสคำที่ไม่เป็นศูนย์ที่มีค่าน้ำหนักน้อยที่สุดจะมีระยะห่างน้อยที่สุดจากรหัสคำที่เป็นศูนย์ และด้วยเหตุนี้จึงเป็นตัวกำหนดระยะห่างน้อยที่สุดของรหัส

ระยะทางdของรหัสเชิงเส้นCยังเท่ากับจำนวนคอลัมน์ที่ขึ้นต่อกันเชิงเส้นขั้นต่ำของเมทริกซ์ตรวจสอบHด้วย

บทพิสูจน์:เนื่องจาก ซึ่งเทียบเท่ากับโดยที่คือคอลัมน์ของลบรายการที่ มี ออก รายการ ที่มีเป็นอิสระเชิงเส้น ดังนั้น จึงเป็นจำนวนคอลัมน์ที่เป็นอิสระเชิงเส้นอย่างน้อยที่สุด ในทางกลับกัน พิจารณาเซตของคอลัมน์ที่เป็นอิสระเชิงเส้นขั้นต่ำโดยที่คือเซตของดัชนีคอลัมน์ ตอนนี้พิจารณาเวกเตอร์เช่นถ้าสังเกตว่า เนื่องจากดังนั้น เราจึงมีซึ่งเป็นจำนวนคอลัมน์ที่เป็นอิสระเชิงเส้นขั้นต่ำในคุณสมบัติที่กล่าวอ้างจึงได้รับการพิสูจน์แล้ว ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}$${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}$${\displaystyle {\boldสัญลักษณ์ {H_{i}}}}$${\displaystyle i^{th}}$${\displaystyle {\boldสัญลักษณ์ {H}}}$${\displaystyle c_{i}=0}$${\displaystyle {\boldสัญลักษณ์ {H_{i}}}}$${\displaystyle c_{i}\neq 0}$${\displaystyle d}$${\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}$${\displaystyle S}$${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}$${\displaystyle {\boldสัญลักษณ์ {c'}}}$${\displaystyle c_{j}'=0}$${\displaystyle j\notin S}$${\displaystyle {\boldsymbol {c'}}\in C}$${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}$${\displaystyle d\leq wt({\boldsymbol {c'}})}$${\displaystyle {\boldsymbol {H}}}$

รหัสแฮมมิงเป็นรหัสเชิงเส้นประเภทแรกที่พัฒนาขึ้นเพื่อแก้ไขข้อผิดพลาด และถูกนำมาใช้กันอย่างแพร่หลายในระบบสื่อสารดิจิทัล สำหรับจำนวนเต็มบวกใดๆ จะมีรหัสแฮมมิง อยู่หนึ่งรหัส เนื่องจากรหัสแฮมมิงนี้สามารถแก้ไขข้อผิดพลาด 1 บิตได้ ${\displaystyle r\geq 2}$${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}$${\displaystyle d=3}$

ตัวอย่าง:รหัสบล็อกเชิงเส้นที่มีเมทริกซ์ตัวสร้างและเมทริกซ์ตรวจสอบความเท่าเทียมกันดังต่อไปนี้ คือรหัสแฮมมิง ${\displaystyle [7,4,3]_{2}}$

${\displaystyle {\boldsymbol {G}}={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&0&1&1\\0&0&1&0&1&1&1\\0&0&0&1&1&0&1\end{pmatrix}},}$${\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}$

รหัส Hadamardเป็นรหัสเชิงเส้นและสามารถแก้ไขข้อผิดพลาดได้หลายอย่าง รหัส Hadamard สามารถสร้างได้ทีละคอลัมน์ โดยคอลัมน์คือบิตของการแสดงเลขฐานสองของจำนวนเต็มดังแสดงในตัวอย่างต่อไปนี้ รหัส Hadamard มีระยะห่างน้อยที่สุดดังนั้นจึงสามารถแก้ไขข้อผิดพลาด ได้${\displaystyle [2^{r},r,2^{r-1}]_{2}}$${\displaystyle i^{th}}$${\displaystyle i}$${\displaystyle 2^{r-1}}$${\displaystyle 2^{r-2}-1}$

ตัวอย่าง: รหัสบล็อกเชิงเส้นที่มีเมทริกซ์กำเนิดต่อไปนี้เป็นรหัส Hadamard: . ${\displaystyle [8,3,4]_{2}}$${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }={\begin{pmatrix}0&0&0&0&1&\ 1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix}}}$

รหัส Hadamardเป็นกรณีพิเศษของรหัส Reed–Mullerถ้าเรานำคอลัมน์แรก (คอลัมน์ที่มีค่าเป็นศูนย์ทั้งหมด) ออกจากรหัส Hadamard เราจะได้รหัส simplexซึ่งเป็นรหัสคู่ขนานของรหัส Hamming ${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}$${\displaystyle [7,3,4]_{2}}$

พารามิเตอร์ d มีความเกี่ยวข้องอย่างใกล้ชิดกับความสามารถในการแก้ไขข้อผิดพลาดของรหัส โครงสร้าง/อัลกอริทึมต่อไปนี้แสดงให้เห็นถึงสิ่งนี้ (เรียกว่าอัลกอริทึมการถอดรหัสเพื่อนบ้านที่ใกล้ที่สุด):

อินพุต: เวกเตอร์ที่ได้รับ v ใน${\displaystyle \mathbb {F} _{q}^{n}.}$

ผลลัพธ์: รหัสคำที่ใกล้เคียงที่สุดกับ(ถ้ามี) ${\displaystyle w}$${\displaystyle C}$${\displaystyle v}$

• เริ่มต้นด้วยให้ทำซ้ำสองขั้นตอนต่อไปนี้${\displaystyle t=0}$
• ระบุองค์ประกอบของทรงกลมรัศมี (แฮมมิง) รอบคำที่ได้รับซึ่งแสดงด้วย ${\displaystyle t}$${\displaystyle v}$${\displaystyle B_{t}(v)}$
  • สำหรับแต่ละค่าในให้ตรวจสอบว่าอยู่ใน หรือไม่ ถ้าใช่ ให้ส่งคืนเป็นคำตอบ${\displaystyle w}$${\displaystyle B_{t}(v)}$${\displaystyle w}$${\displaystyle C}$${\displaystyle w}$
• เพิ่มค่าขึ้น. ล้มเหลวเฉพาะเมื่อการแจงนับเสร็จสมบูรณ์แล้วและไม่พบวิธีแก้ปัญหาใดๆ${\displaystyle t}$${\displaystyle t>(d-1)/2}$

เรากล่าวว่าตัวแก้ไขเชิงเส้นนั้นแก้ไขข้อผิดพลาดได้ หากมีคำรหัสอย่างมากที่สุดหนึ่งคำในสำหรับแต่ละ ใน${\displaystyle C}$${\displaystyle t}$${\displaystyle B_{t}(v)}$${\displaystyle v}$${\displaystyle \mathbb {F} _{q}^{n}}$

โดยทั่วไป รหัสต่างๆมักจะใช้ตัวอักษรC แทน และรหัสที่มีความยาวnและมีอันดับk (กล่าวคือ มี คำรหัส nคำในฐาน และมี แถว kแถวในเมทริกซ์กำเนิด ) มักจะเรียกว่า รหัส ( n ,  k ) รหัสบล็อกเชิงเส้นมักจะใช้สัญลักษณ์เป็นรหัส [ n ,  k ,  d ] โดยที่ dหมายถึงระยะทางแฮมมิงขั้นต่ำระหว่างคำรหัสสองคำใดๆ ของรหัสนั้น

(สัญลักษณ์ [ n ,  k ,  d ] ไม่ควรสับสนกับสัญลักษณ์ ( n ,  M ,  d ) ที่ใช้ในการระบุรหัสที่ไม่เป็นเชิงเส้นที่มีความยาวnขนาดM (กล่าวคือ มี คำรหัส Mคำ) และระยะห่างแฮมมิงขั้นต่ำd )

บทพิสูจน์ย่อย ( ขอบเขตซิงเกิลตัน ): รหัสเชิงเส้น [ n , k , d ] ทุกตัว C สอดคล้องกับเงื่อนไขต่อไปนี้ ${\displaystyle k+d\leq n+1}$

รหัสCที่มีพารามิเตอร์ที่สอดคล้องกับk  + d  =  n  + 1 เรียกว่ารหัสที่แยกได้ด้วยระยะทางสูงสุดหรือMDSรหัสดังกล่าว หากมีอยู่จริง ก็ถือว่าเป็นรหัสที่ดีที่สุดเท่าที่จะเป็นไปได้ในบางแง่

ถ้าC ₁และC ₂เป็นรหัสสองรหัสที่มีความยาวnและถ้ามีการเรียงสับเปลี่ยนpในกลุ่มสมมาตรS _nซึ่ง ( c ₁ ,..., c _n ) ในC ₁ ก็ต่อเมื่อ ( c _{p (1)} ,..., c _{p ( n )} ) ในC ₂แล้ว เราจะกล่าวว่าC ₁และC ₂สมมูลกันโดยการเรียงสับเปลี่ยนโดยทั่วไปแล้ว ถ้ามีเมทริกซ์เอกนามที่ส่งC ₁ไปยังC ₂ อย่างสมมาตร เราจะกล่าวว่า C ₁และC ₂สมมูลกัน${\displaystyle n\times n}$${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$

ทฤษฎีบทเสริม : รหัสเชิงเส้นใดๆ จะเทียบเท่ากับการเรียงสับเปลี่ยนของรหัสที่อยู่ในรูปแบบมาตรฐาน

รหัสจะถูกกำหนดให้เป็นรหัสที่มีระยะห่างเท่ากันก็ต่อเมื่อมีค่าคงที่d บางค่าที่ทำให้ระยะห่างระหว่างคำรหัสที่แตกต่างกันสอง คำใดๆ ของรหัสเท่ากับd ^{[ 4 ]}ในปี พ.ศ. 2527 Arrigo Bonisoli ได้กำหนดโครงสร้างของรหัสเชิงเส้นที่มีน้ำหนักหนึ่งตัวเหนือฟิลด์จำกัดและพิสูจน์ว่ารหัสเชิงเส้นที่มีระยะห่างเท่ากันทุกรหัสเป็นลำดับของรหัสHamming คู่^{[ 5 ]}

ตัวอย่างของรหัสเชิงเส้น ได้แก่:

ปริภูมิแฮมมิงเหนือตัวอักษรที่ไม่ใช่ฟิลด์ก็ได้รับการพิจารณาเช่นกัน โดยเฉพาะอย่างยิ่งเหนือวงแหวนจำกัดโดยเฉพาะอย่างยิ่งวงแหวนกาโลอิสเหนือZ ₄ซึ่งทำให้เกิดโมดูลแทนปริภูมิเวกเตอร์และรหัสเชิงเส้นวงแหวน (ระบุด้วยโมดูลย่อย ) แทนรหัสเชิงเส้น เมตริกทั่วไปที่ใช้ในกรณีนี้คือระยะทางลีมีไอโซเมตรีเกรย์ระหว่าง(เช่น GF(2 ^{2 m} )) กับระยะทางแฮมมิงและ(เรียกอีกอย่างว่า GR(4,m)) กับระยะทางลี จุดเด่นหลักคือการสร้างความสัมพันธ์ระหว่างรหัส "ดี" บางรหัสที่ไม่เป็นเชิงเส้นเหนือเป็นภาพของรหัสเชิงเส้นวงแหวนจาก^{[ 6 ] [ 7 ] [ 8 ]}${\displaystyle \mathbb {Z} _{2}^{2m}}$${\displaystyle \mathbb {Z} _{4}^{m}}$${\displaystyle \mathbb {Z} _{2}^{2m}}$${\displaystyle \mathbb {Z} _{4}^{m}}$

ผู้เขียนบางคนเรียกโค้ดดังกล่าวบนวงแหวนว่าโค้ดเชิงเส้นเช่นกัน^{[ 9 ]}

• วิธีการถอดรหัส

• โปรแกรมสร้างรหัสq -ary
• ตารางรหัส: ขอบเขตบนพารามิเตอร์ของรหัสประเภทต่างๆ , IAKS, Fakultät für Informatik, Universität Karlsruhe (TH) ] ตารางออนไลน์ที่ทันสมัยของรหัสไบนารี่ที่ดีที่สุด รวมถึงรหัสที่ไม่ใช่ไบนารี่
• ฐานข้อมูลรหัส Z4ออนไลน์ ฐานข้อมูลรหัส Z4 ที่เหมาะสมที่สุดที่อัปเดตอยู่เสมอ