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

ในทางตรงกันข้ามรหัสที่ถอดรหัสได้ในระดับท้องถิ่นจะใช้บิตจำนวนเล็กน้อยของคำรหัสเพื่อ กู้คืนข้อมูลดั้งเดิม โดยอาศัยความน่าจะเป็น สัดส่วนของข้อผิดพลาดจะเป็นตัวกำหนดว่าตัวถอดรหัสจะกู้คืนบิตดั้งเดิมได้อย่างถูกต้องมากน้อยเพียงใด อย่างไรก็ตาม ไม่ใช่รหัสที่ถอดรหัสได้ในระดับท้องถิ่นทั้งหมดที่จะทดสอบได้ในระดับท้องถิ่น^{[ 1 ]}

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

ระยะแฮมมิง (Hamming distance)ใช้ ในการวัดระยะห่างระหว่างสายสองเส้น

${\displaystyle \Delta (x,y)=|\{i:x_{i}\neq y_{i}\}|}$

ระยะห่างของสตริงจากรหัสคำนวณโดย ${\displaystyle w}$${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$

${\displaystyle \Delta (w,C)=\min _{x}\{\Delta (w,C(x))\}}$

ระยะทางสัมพัทธ์คำนวณจากเศษส่วนของจำนวนบิต

${\displaystyle \delta (x,y)=\Delta (x,y)/n{\text{ and }}\delta (w,C)=\Delta (w,C)/n}$

รหัสเรียกว่า-local -testable หากมีเครื่องจักรทัวริง M ที่ได้รับการเข้าถึงแบบสุ่มไปยังอินพุตที่ทำการสอบถามแบบไม่ปรับตัวได้ไม่เกินและเป็นไปตามเงื่อนไขต่อไปนี้: ^{[ 2 ]}${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$${\displaystyle q}$${\displaystyle \delta }$${\displaystyle w}$${\displaystyle q}$${\displaystyle w}$

• สำหรับค่าใดๆ ของและ, . กล่าวอีกนัยหนึ่ง M ยอมรับการเข้าถึงรหัสคำใดๆ ของ C${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle w=C(x)}$${\displaystyle Pr[M^{w}(1^{k})=1]=1}$
• สำหรับเงื่อนไขดังกล่าวM จะต้องปฏิเสธสตริงที่อยู่ห่างจาก C อย่างน้อยครึ่งหนึ่งของเวลา${\displaystyle w\in \{0,1\}^{n}}$${\displaystyle \delta (w,C)>\delta }$${\displaystyle Pr[M^{w}(1^{k})=1]\leq 1/2}$${\displaystyle \delta }$

นอกจากนี้ อัตราของรหัสยังหมายถึงอัตราส่วนระหว่างความยาวของข้อความและความยาวของคำรหัสด้วย

${\displaystyle r={\frac {|x|}{|C(x)|}}}$

ยังคงเป็นคำถามที่เปิดกว้างว่ามีรหัสทดสอบในท้องถิ่นที่มีขนาดเชิงเส้นหรือไม่ แต่มีโครงสร้างหลายอย่างที่ถือว่า "เกือบเป็นเชิงเส้น": ^{[ 3 ]}

1. พหุนามที่ใกล้เคียงกับเชิงเส้นอย่างไม่จำกัด สำหรับค่าใดๆก็ตาม${\displaystyle \epsilon >0}$${\displaystyle n=k^{1+\epsilon }}$
2. ฟังก์ชันในรูปแบบโดยที่เป็นฟังก์ชันที่มีแนวโน้มเข้าใกล้ 0 ซึ่งทำให้ n มีลักษณะเป็นเชิงเส้นมากขึ้นเมื่อ k เพิ่มขึ้น ตัวอย่างเช่น: ${\displaystyle n=k^{1+\epsilon (k)}}$${\displaystyle \epsilon (k)}$
   • ${\displaystyle 1/\log \log k}$
   • ${\displaystyle 1/(\log k)^{c}}$สำหรับบางคน${\displaystyle c\in (0,1)}$
   • ${\displaystyle \exp((\log \log \log k)^{c})/\log k}$สำหรับ${\displaystyle c\in (0,1)}$

สิ่งเหล่านี้บรรลุผลสำเร็จได้ทั้งสองอย่าง แม้จะมีความซับซ้อนในการสอบถามคงที่และตัวอักษร ไบนารี เช่นเดียวกับสำหรับใดๆเป้าหมายเชิงเส้นใกล้เคียงถัดไปคือเชิงเส้นจนถึงปัจจัยพหุโลการิทึมยังไม่มีใครคิดค้นโค้ดที่ทดสอบได้เชิงเส้นที่ตรงตามข้อจำกัดนี้ได้^{[ 3 ]}${\displaystyle n=k^{1+1/(\log k)^{c}}}$${\displaystyle c\in (0,1)}$${\displaystyle n={\text{poly}}(\log k)*k}$

ในเดือนพฤศจิกายน 2021 มีรายงานเอกสารก่อนตีพิมพ์สองฉบับ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} เกี่ยวกับ การสร้าง " -LTCs" ในเวลาพหุนามเป็นครั้งแรกซึ่งก็คือรหัสที่ทดสอบได้ในระดับท้องถิ่นที่มีอัตราคงที่ระยะทางคงที่และความเฉพาะที่คงที่ ${\displaystyle c^{3}}$${\displaystyle r}$${\displaystyle \delta }$${\displaystyle q}$

รหัสที่ทดสอบได้ในระดับท้องถิ่นมีหลายอย่างที่คล้ายคลึงกับหลักฐานที่ตรวจสอบได้ด้วยความน่าจะเป็น (PCP) สิ่งนี้ควรเห็นได้ชัดจากความคล้ายคลึงกันของโครงสร้าง ในทั้งสองกรณี เราจะได้รับคำถามแบบสุ่มที่ไม่ปรับเปลี่ยนได้ในสตริงขนาดใหญ่ และหากเราต้องการยอมรับ เราต้องยอมรับด้วยความน่าจะเป็น 1 และหากไม่ยอมรับ เราต้องยอมรับไม่เกินครึ่งหนึ่งของเวลา ความแตกต่างที่สำคัญคือ PCP สนใจที่จะยอมรับก็ต่อเมื่อมีอยู่จริง ที่ ทำให้ในขณะที่รหัสที่ทดสอบได้ในระดับท้องถิ่นจะยอมรับก็ต่อเมื่อมันเป็นส่วนหนึ่งของรหัส มีหลายสิ่งหลายอย่างที่อาจผิดพลาดได้ในการสมมติว่าหลักฐาน PCP เข้ารหัสรหัสที่ทดสอบได้ในระดับท้องถิ่น ตัวอย่างเช่น คำจำกัดความของ PCP ไม่ได้กล่าวถึงหลักฐานที่ไม่ถูกต้อง แต่กล่าวถึงเฉพาะอินพุตที่ไม่ถูกต้องเท่านั้น ${\displaystyle q}$${\displaystyle x}$${\displaystyle w}$${\displaystyle M^{w}(x)=1}$${\displaystyle w}$

แม้จะมีความแตกต่างกัน แต่รหัสที่ทดสอบได้ในท้องถิ่นและ PCP ก็มีความคล้ายคลึงกันมากพอที่บ่อยครั้งเมื่อสร้างอันหนึ่ง ผู้พิสูจน์จะสร้างอีกอันหนึ่งไปพร้อมกัน^{[ 8 ]}

รหัส Hadamard ซึ่ง เป็นหนึ่งในรหัสแก้ไขข้อผิดพลาดที่มีชื่อเสียงที่สุดเป็นรหัสที่ทดสอบได้ในระดับท้องถิ่น คำรหัส x ถูกเข้ารหัสในรหัส Hadamard ให้เป็นฟังก์ชันเชิงเส้น(mod 2) ซึ่งต้องแสดงผลลัพธ์ของฟังก์ชันนี้สำหรับทุกค่า y ที่เป็นไปได้ ซึ่งต้องใช้บิตมากกว่าอินพุตแบบทวีคูณ ในการทดสอบว่าสตริง w เป็นคำรหัสของรหัส Hadamard หรือไม่ สิ่งที่เราต้องทำคือทดสอบว่าฟังก์ชันที่เข้ารหัสเป็นฟังก์ชันเชิงเส้นหรือไม่ ซึ่งหมายถึงการตรวจสอบว่าx และ y เป็น เวกเตอร์ สุ่มแบบสม่ำเสมอ หรือ ไม่ (โดยที่หมายถึงการดำเนินการ XOR ระดับบิต ) ${\displaystyle f(y)={\sum _{i}{x_{i}y_{i}}}}$${\displaystyle w(x)\oplus w(y)=w(x\oplus y)}$${\displaystyle \oplus }$

เป็นเรื่องง่ายที่จะเห็นว่าสำหรับการเข้ารหัสที่ถูกต้องใดๆสมการนี้เป็นจริง เนื่องจากนั่นคือนิยามของฟังก์ชันเชิงเส้น อย่างไรก็ตาม สิ่งที่ยากกว่าเล็กน้อยคือการแสดงให้เห็นว่าสตริงที่อยู่ห่างจาก C มาก จะมีขอบเขตบนของข้อผิดพลาดในแง่ของขอบเขตหนึ่งพบได้โดยวิธีการโดยตรงในการประมาณโอกาสที่การตรวจสอบหนึ่งในสามครั้งจะให้ผลลัพธ์ที่ไม่ถูกต้อง ให้ A, B และ C เป็นเหตุการณ์ที่, , และไม่ถูกต้อง ให้ E เป็นเหตุการณ์ที่เหตุการณ์ใดเหตุการณ์หนึ่งเกิดขึ้น ซึ่งจะได้ผลลัพธ์เป็น ${\displaystyle w}$${\displaystyle \delta }$${\displaystyle \delta }$${\displaystyle w(x)}$${\displaystyle w(y)}$${\displaystyle w(x\oplus y)}$

${\displaystyle {\begin{aligned}P(E)&\geq P(A\cup B\cup C)-3*P(A\cup B)\\&\geq 3*P(A)-3*P(A\cup B)-3*P(A\cup B)\\&\geq 3\delta -6\delta ^{2}\end{aligned}}}$

วิธีนี้ใช้ได้ผลสำหรับแต่หลังจากนั้นไม่นานด้วยการทำงานเพิ่มเติม สามารถแสดงให้เห็นได้ว่าข้อผิดพลาดมีขอบเขตจำกัดโดย ${\displaystyle 0<\delta \leq 5/16}$${\displaystyle 3\delta -6\delta ^{2}<\delta }$

${\displaystyle f(x)={\begin{cases}3\delta -6\delta ^{2}&:0\leq \delta \leq 5/16\\45/128&:5/16\leq \delta \leq 45/128\\\delta &:45/128\leq \delta \leq 1/2\end{cases}}}$

สำหรับค่าที่กำหนดใดๆ ก็ตามโอกาสที่จะเกิดผลบวกเท็จจะมีค่าคงที่เท่านั้น ดังนั้นเราจึงสามารถตรวจสอบจำนวนครั้งคงที่เพื่อให้ได้ความน่าจะเป็นที่ต่ำกว่า 1/2 ได้^{[ 3 ]}${\displaystyle \delta }$

รหัสยาวเป็นรหัสอีกแบบหนึ่งที่มีการขยายตัวขนาดใหญ่มาก ซึ่งใกล้เคียงกับการทดสอบในระดับท้องถิ่น เมื่อได้รับอินพุต(โปรดทราบว่าต้องใช้บิตในการแสดง) ฟังก์ชันที่ส่งคืนบิตของอินพุตจะถูกประเมินบนอินพุต -บิต ที่เป็นไปได้ทั้งหมด และรหัสคำคือการต่อกันของสิ่งเหล่านี้ (ความยาว) วิธีการทดสอบในระดับท้องถิ่นโดยมีข้อผิดพลาดบ้างคือการเลือกอินพุตแบบสุ่มอย่างสม่ำเสมอและตั้งค่าแต่มีโอกาสเล็กน้อยที่จะพลิกบิตแต่ละบิตยอมรับฟังก์ชันเป็นรหัสคำหากถ้าเป็นรหัสคำ ระบบจะยอมรับตราบใดที่ไม่เปลี่ยนแปลง ซึ่งเกิดขึ้นด้วยความน่าจะเป็น สิ่งนี้ละเมิดข้อกำหนดที่ว่ารหัสคำจะต้องได้รับการยอมรับเสมอ แต่ก็อาจดีพอสำหรับความต้องการบางอย่าง^{[ 9 ]}${\displaystyle 0\leq i\leq 2^{k}}$${\displaystyle k}$${\displaystyle i^{th}}$${\displaystyle f_{i}(x)=x_{i}}$${\displaystyle 2^{k}}$${\displaystyle 0\leq x\leq 2^{2^{k}}}$${\displaystyle n=2^{2^{k}}}$${\displaystyle x}$${\displaystyle y=x}$${\displaystyle \mu >0}$${\displaystyle f}$${\displaystyle f(x)=f(y)}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x_{i}}$${\displaystyle 1-\mu }$

รหัสที่สามารถทดสอบได้ในระดับท้องถิ่นอื่นๆ ได้แก่รหัสรีด-มุลเลอร์ (ดูรหัสที่ถอดรหัสได้ในระดับท้องถิ่นสำหรับอัลกอริธึมการถอดรหัส) รหัสรีด-โซโลมอนและรหัสสั้น

• กิลเบิร์ต-วาร์ชามอฟ ผูกพัน
• รหัสแฮมมิง
• รหัสขยาย

• "ความก้าวหน้าครั้งสำคัญ — รหัสที่ทดสอบได้ ในระดับท้องถิ่นด้วยอัตรา ระยะทาง และความเฉพาะที่คงที่ | สถาบันไซมอนส์เพื่อทฤษฎีการคำนวณ" simons.berkeley.edu 6 ตุลาคม 2021