การเข้ารหัสช่วง (หรือการเข้ารหัสช่วง ) เป็น วิธี การเข้ารหัสเอนโทรปีที่กำหนดโดย G. Nigel N. Martin ในเอกสารปี 1979 ^{[ 1 ]}ซึ่งค้นพบรหัสเลขคณิต FIFO อีกครั้งซึ่งแนะนำโดย Richard Clark Pasco ในปี 1976 ^{[ 2 ]}เมื่อกำหนดสตรีมของสัญลักษณ์และความน่าจะเป็นของสัญลักษณ์เหล่านั้น ตัวเข้ารหัสช่วงจะสร้างสตรีมของบิตที่มีประสิทธิภาพด้านพื้นที่เพื่อแสดงสัญลักษณ์เหล่านี้ และเมื่อกำหนดสตรีมและความน่าจะเป็น ตัวถอดรหัสช่วงจะกลับกระบวนการดังกล่าว

การเข้ารหัสช่วงคล้ายกับการเข้ารหัสเลขคณิต มาก ยกเว้นว่าการเข้ารหัสทำด้วยตัวเลขในฐานใดก็ได้ แทนที่จะใช้บิต ดังนั้นจึงเร็วกว่าเมื่อใช้ฐานที่ใหญ่กว่า (เช่นไบต์ ) โดยมีค่าใช้จ่ายเล็กน้อยในด้านประสิทธิภาพการบีบอัด^{[ 3 ]}หลังจากสิทธิบัตรการเข้ารหัสเลขคณิตฉบับแรก (ปี 1978) หมดอายุ^{[ 4 ]}การเข้ารหัสช่วงก็ปรากฏว่าปราศจากข้อจำกัดทางสิทธิบัตรอย่างชัดเจน สิ่งนี้กระตุ้นความสนใจในเทคนิคนี้ใน ชุมชน โอเพนซอร์ส เป็นอย่างมาก นับตั้งแต่นั้นมา สิทธิบัตรเกี่ยวกับเทคนิคการเข้ารหัสเลขคณิตที่รู้จักกันดีต่างๆ ก็หมดอายุลงเช่นกัน

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

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

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

สมมติว่าเราต้องการเข้ารหัสข้อความ "AABA<EOM>" โดยที่ <EOM> คือสัญลักษณ์สิ้นสุดข้อความ สำหรับตัวอย่างนี้ ถือว่าตัวถอดรหัสรู้ว่าเราตั้งใจจะเข้ารหัสสัญลักษณ์ห้าตัวในระบบเลขฐาน 10 (โดยอนุญาตให้ มีการรวมกันของสัญลักษณ์ที่แตกต่างกัน ^10⁵แบบในช่วง [0, 100000)) โดยใช้การแจกแจงความน่าจะเป็น {A: .60; B: .20; <EOM>: .20} ตัวเข้ารหัสจะแบ่งช่วง [0, 100000) ออกเป็นสามช่วงย่อย:

A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000) 

เนื่องจากสัญลักษณ์แรกของเราคือ A จึงทำให้ช่วงเริ่มต้นของเราลดลงเหลือ [0, 60000) การเลือกสัญลักษณ์ที่สองทำให้เราเหลือช่วงย่อยสามช่วงของช่วงนี้ เราจะแสดงช่วงย่อยเหล่านั้นต่อจาก 'A' ที่เข้ารหัสไว้แล้ว:

AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000) 

เมื่อเข้ารหัสสัญลักษณ์สองตัวแล้ว ช่วงของเราจึงอยู่ที่ [0, 36000) และสัญลักษณ์ตัวที่สามนำไปสู่ตัวเลือกต่อไปนี้:

AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000) 

คราวนี้ ตัวเลือกที่สองจากสามตัวเลือกของเราเป็นตัวแทนของข้อความที่เราต้องการเข้ารหัส และช่วงของเราจึงเป็น [21600, 28800) การกำหนดช่วงย่อยในกรณีนี้อาจดูยากขึ้น แต่จริงๆ แล้วไม่ยากเลย: เราเพียงแค่ลบขอบล่างออกจากขอบบนเพื่อหาว่ามีตัวเลข 7200 ตัวในช่วงของเรา โดย 4320 ตัวแรกคิดเป็น 0.60 ของทั้งหมด 1440 ตัวถัดไปคิดเป็น 0.20 ถัดไป และ 1440 ตัวที่เหลือคิดเป็น 0.20 ที่เหลือของทั้งหมด การบวกขอบล่างกลับเข้าไปจะทำให้เราได้ช่วงของเรา:

AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800) 

สุดท้ายนี้ เมื่อเราจำกัดช่วงให้แคบลงเหลือเพียง [21600, 25920) เราก็เหลือสัญลักษณ์อีกเพียงตัวเดียวที่จะต้องเข้ารหัส โดยใช้เทคนิคเดียวกันกับที่ใช้ก่อนหน้านี้ในการแบ่งช่วงระหว่างขอบล่างและขอบบน เราพบว่าช่วงย่อยทั้งสามช่วงมีดังนี้:

AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920) 

และเนื่องจาก <EOM> เป็นสัญลักษณ์สุดท้ายของเรา ช่วงสุดท้ายของเราจึงเป็น [25056, 25920) เนื่องจากจำนวนเต็มห้าหลักทั้งหมดที่ขึ้นต้นด้วย "251" อยู่ในช่วงสุดท้ายของเรา จึงเป็นหนึ่งในคำนำหน้าสามหลักที่เราสามารถส่งได้ซึ่งจะสื่อความหมายข้อความเดิมของเราได้อย่างชัดเจน (ข้อเท็จจริงที่ว่ามีคำนำหน้าดังกล่าวทั้งหมดแปดคำแสดงว่าเรายังคงมีข้อบกพร่องอยู่ ซึ่งเกิดจากการที่เราใช้ฐาน 10แทนที่จะเป็นฐาน 2 )

ปัญหาหลักอาจดูเหมือนเป็นการเลือกช่วงเริ่มต้นที่ใหญ่พอที่จะทำให้ไม่ว่าเราต้องเข้ารหัสสัญลักษณ์กี่ตัว เราก็จะมีช่วงปัจจุบันที่ใหญ่พอที่จะแบ่งออกเป็นช่วงย่อยที่ไม่เป็นศูนย์ได้เสมอ อย่างไรก็ตาม ในทางปฏิบัติแล้ว นี่ไม่ใช่ปัญหา เพราะแทนที่จะเริ่มต้นด้วยช่วงที่ใหญ่มากและค่อยๆ ลดขนาดลง ตัวเข้ารหัสจะทำงานกับช่วงตัวเลขที่เล็กกว่าในแต่ละครั้ง หลังจากเข้ารหัสตัวเลขจำนวนหนึ่งแล้ว ตัวเลขทางซ้ายสุดจะไม่เปลี่ยนแปลง ในตัวอย่าง หลังจากเข้ารหัสเพียงสามสัญลักษณ์ เราก็รู้แล้วว่าผลลัพธ์สุดท้ายของเราจะเริ่มต้นด้วย "2" ตัวเลขเพิ่มเติมจะถูกเลื่อนเข้ามาทางด้านขวาเมื่อตัวเลขทางซ้ายถูกส่งออกไป ดังแสดงในโค้ดต่อไปนี้:

int low = 0 ; int range = 100000 ;void Run () { Encode ( 0 , 6 , 10 ); // A Encode ( 0 , 6 , 10 ); // A Encode ( 6 , 2 , 10 ); // B Encode ( 0 , 6 , 10 ); // A Encode ( 8 , 2 , 10 ); // <EOM>// ปล่อยตัวเลขหลักสุดท้าย - ดูด้านล่างในขณะที่( ช่วง< 10000 ) EmitDigit ();low += 10000 ; EmitDigit (); }void EmitDigit ( ) { Console.Write ( low / 10000 ); low = ( low % 10000 ) * 10 ; range * = 10 ; }void Encode ( int start , int size , int total ) { // ปรับช่วงตามช่วงของสัญลักษณ์range /= total ; low += start * range ; range *= size ;// ตรวจสอบว่าตัวเลขหลักซ้ายสุดเหมือนกันตลอดช่วงหรือไม่ในขณะที่( low / 10000 == ( low + range ) / 10000 ) EmitDigit ();// ปรับช่วงใหม่ - ดูเหตุผลด้านล่างหาก( ช่วง< 1000 ) { EmitDigit (); EmitDigit (); ช่วง= 100000 - ต่ำ; } }

สุดท้ายนี้ เราอาจต้องเพิ่มตัวเลขอีกสองสามหลัก ตัวเลขหลักบนสุดของlowอาจจะเล็กเกินไป ดังนั้นเราต้องเพิ่มค่าขึ้น แต่เราต้องแน่ใจว่าเราจะไม่เพิ่มค่าเกินlow+rangeดังนั้นก่อนอื่นเราต้องตรวจสอบให้แน่ใจว่าrangeมีค่ามากพอ

// ปล่อยตัวเลขหลักสุดท้ายในขณะที่( ช่วง< 10000 ) EmitDigit ();low += 10000 ; EmitDigit ();

ปัญหาหนึ่งที่อาจเกิดขึ้นกับEncodeฟังก์ชันข้างต้นคือ ค่าที่ได้rangeอาจมีขนาดเล็กมาก แต่ ตัวเลขหลักแรก lowยังlow+rangeคงแตกต่างกัน ซึ่งอาจส่งผลให้ช่วงความแม่นยำไม่เพียงพอที่จะแยกแยะสัญลักษณ์ทั้งหมดในตัวอักษรได้ เมื่อเกิดเหตุการณ์เช่นนี้ เราจำเป็นต้องปรับแก้เล็กน้อย โดยแสดงตัวเลขหลักแรกสองสามหลัก แม้ว่าอาจจะคลาดเคลื่อนไปหนึ่งหลัก และปรับช่วงใหม่เพื่อให้มีพื้นที่มากที่สุดเท่าที่จะเป็นไปได้

ตัวอย่างเช่น ลองนึกภาพว่ากระแสข้อมูลขาเข้าทำให้ตัวเข้ารหัสได้ช่วงเปิดขวา [59888, 60188) นั่นคือlow = 59888และrange = 300เทคนิคคือการจำกัดช่วงให้แคบลงเหลือ [59888, 60000) = [ 59 888, 59 999] ซึ่งจะทำให้ตัวเข้ารหัสสามารถส่ง ค่า ตัวเลขสองหลักซ้ายสุดของlowและปรับช่วงใหม่เป็น [88800, 99999] = [88800, 100000) นั่นคือlow = 88800และrange = 100000 - low

ตัวถอดรหัสจะทำตามขั้นตอนเดียวกัน ดังนั้นมันจะรู้ว่าเมื่อใดที่ต้องทำเช่นนี้เพื่อให้ข้อมูลตรงกัน

// ส่วนนี้จะอยู่ก่อนสิ้นสุดฟังก์ชัน Encode() ด้านบนหาก( range < 1000 ) { EmitDigit (); EmitDigit (); range = 100000 - low ; }

ในตัวอย่างนี้ใช้ฐาน 10 แต่ในการใช้งานจริงจะใช้เลขฐานสอง โดยใช้ช่วงข้อมูลเต็มรูปแบบของชนิดข้อมูลจำนวนเต็มดั้งเดิม แทนที่จะใช้ `undefined` 10000และ ` undefined` 1000คุณอาจใช้ค่าคงที่เลขฐานสิบหก เช่น ` undefined` 0x1000000และ ` 0x10000undefined` แทนที่จะส่งค่าตัวเลขทีละหลัก คุณจะส่งค่าไบต์ทีละไบต์และใช้การเลื่อนไบต์แทนการคูณด้วย 10

การถอดรหัสใช้ขั้นตอนวิธีเดียวกันทุกประการ โดยเพิ่มเติมคือการติดตามcodeค่าปัจจุบันซึ่งประกอบด้วยตัวเลขที่อ่านได้จากตัวบีบอัด แทนที่จะส่งตัวเลขหลักบนสุดlowออกไป คุณก็แค่ทิ้งมันไป แต่คุณยังเลื่อนตัวเลขหลักบนสุดของออกไปcodeและเลื่อนตัวเลขใหม่ที่อ่านได้จากตัวบีบอัดเข้ามา ใช้ ด้าน ล่าง AppendDigitแทนEmitDigit

int code = 0 ; int low = 0 ; int range = 1 ;void InitializeDecoder () { AppendDigit (); // ในโค้ดตัวอย่างนี้ จริงๆ แล้วต้องการแค่ตัวเดียวAppendDigit (); AppendDigit (); AppendDigit (); AppendDigit (); }void AppendDigit () { code = ( code % 10000 ) * 10 + ReadNextDigit (); low = ( low % 10000 ) * 10 ; range *= 10 ; }void Decode ( int start , int size , int total ) // Decode เหมือนกับ Encode โดยแทนที่ EmitDigit ด้วย AppendDigit { // ปรับช่วงตามช่วงของสัญลักษณ์range /= total ; low += start * range ; range *= size ;// ตรวจสอบว่าตัวเลขหลักซ้ายสุดเหมือนกันตลอดช่วงหรือไม่ในขณะที่( low / 10000 == ( low + range ) / 10000 ) เพิ่มตัวเลข (AppendDigit ();// ปรับช่วงใหม่ - ดูเหตุผลด้านล่างหาก( ช่วง< 1000 ) { เพิ่มตัวเลข(); เพิ่มตัวเลข(); ช่วง= 100000 - ต่ำ; } }

ในการกำหนดช่วงความน่าจะเป็นที่จะใช้ ตัวถอดรหัสจำเป็นต้องพิจารณาค่าปัจจุบันcodeภายในช่วง [ต่ำ, ต่ำ+ช่วง] และตัดสินใจว่าค่านี้แทนสัญลักษณ์ใด

void Run () { int start = 0 ; int size ; int total = 10 ; InitializeDecoder (); // ต้องได้รับช่วง/ค่ารวม > 0 ในขณะที่start < 8 // หยุดเมื่อได้รับ EOM { int v = GetValue ( total ); // โค้ดอยู่ในช่วงสัญลักษณ์ใด? switch ( v ) // แปลงค่าเป็นสัญลักษณ์{ case 0 : case 1 : case 2 : case 3 : case 4 : case 5 : start = 0 ; size = 6 ; Console.Write ( "A" ) ; break ; case 6 : case 7 : start = 6 ; size = 2 ; Console.Write ( " B" ) ; break ; default : start = 8 ; size = 2 ; Console.WriteLine ( " " ); } Decode ( start , size , total ) ; } }int GetValue ( int total ) { return ( code - low ) / ( range / total ); }

สำหรับตัวอย่าง AABA<EOM> ข้างต้น ฟังก์ชันนี้จะส่งคืนค่าในช่วง 0 ถึง 9 โดยค่า 0 ถึง 5 จะแทน A, 6 และ 7 จะแทน B และ 8 และ 9 จะแทน <EOM>

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

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

• การเข้ารหัสเลขคณิต
• ระบบตัวเลขอสมมาตร
• การบีบอัดข้อมูล
• การเข้ารหัสเอนโทรปี
• การเข้ารหัสฮัฟฟ์แมน
• รูปแบบอิเล็กโทรสรีรวิทยาแบบหลายระดับ
• การเข้ารหัสแชนนอน-ฟาโน

• ตัวเข้ารหัสช่วง
• "ตัวเข้ารหัสช่วง" โดย อาร์ตูโร คัมโปส
• "กายวิภาคของตัวเข้ารหัสช่วง" โดย แอนดรูว์ โพลาร์
• การนำการเข้ารหัสช่วงและ rANS ของ James K. Bonfield ไปใช้อย่างรวดเร็ว
• การใช้งานแบบโอเพนซอร์สที่รวดเร็วของตัวเข้ารหัสช่วงแบบสลับ SSE 4.1 24 บิต