क्रमांक अंकगणित

कई प्रोटोकॉल (कंप्यूटिंग) और एल्गोरिदम को संबंधित संस्थाओं के क्रमांकन या गणना की आवश्यकता होती है। उदाहरण के लिए, एक संचार प्रोटोकॉल को यह पता होना चाहिए कि कोई पैकेट किसी अन्य पैकेट से पहले आता है या बाद में। IETF (इंटरनेट इंजीनियरिंग टास्क फोर्स) RFC 1982 इन अनुक्रम संख्याओं में हेरफेर और तुलना करने के प्रयोजनों के लिए क्रम संख्या अंकगणित को परिभाषित करने का प्रयास करता है। संक्षेप में, जब पूर्ण क्रमांक मान अधिकतम मान के आधे से अधिक घट जाता है (उदाहरण के लिए 8-बिट मान में 128), तो इसे पूर्व के बाद माना जाता है, जबकि अन्य कमी को पहले माना जाता है।

यह कार्य पहले दिखने से कहीं अधिक जटिल है, क्योंकि अधिकांश एल्गोरिदम अनुक्रम संख्याओं के लिए निश्चित आकार (बाइनरी अंक प्रणाली) प्रतिनिधित्व का उपयोग करते हैं। एल्गोरिथम के लिए अक्सर यह महत्वपूर्ण होता है कि जब संख्याएं इतनी बड़ी हो जाएं कि उन्हें आखिरी बार बढ़ाया जाए और उनकी अधिकतम संख्यात्मक सीमाओं के आसपास लपेटा जाए (एक बड़ी सकारात्मक संख्या से 0 या एक बड़ी नकारात्मक संख्या तक तुरंत जाएं) तो वह टूट न जाए। कुछ प्रोटोकॉल इन मुद्दों को अनदेखा करना चुनते हैं और बस अपने काउंटरों के लिए बहुत बड़े पूर्णांकों का उपयोग करते हैं, इस उम्मीद में कि समस्या उत्पन्न होने से पहले प्रोग्राम को बदल दिया जाएगा (या वे रिटायर हो जाएंगे) (वर्ष 2000 समस्या देखें)।

कई संचार प्रोटोकॉल स्लाइडिंग विंडो प्रोटोकॉल के कार्यान्वयन में पैकेट अनुक्रम संख्याओं पर सीरियल नंबर अंकगणित लागू करते हैं। टीसीपी के कुछ संस्करण ट्रांसमिशन कंट्रोल प्रोटोकॉल#टीसीपी टाइमस्टैम्प | का उपयोग करते हैं लपेटे गए अनुक्रम संख्याओं (PAWS) के विरुद्ध सुरक्षा। PAWS अनुक्रम संख्या के उच्च-क्रम बिट्स के विस्तार के रूप में टाइमस्टैम्प का उपयोग करते हुए, पैकेट टाइमस्टैम्प पर समान सीरियल नंबर अंकगणित लागू करता है।

अनुक्रम संख्याओं पर संक्रियाएँ

केवल एक अनुक्रम संख्या में एक छोटे धनात्मक पूर्णांक को जोड़ने और दो अनुक्रम संख्याओं की तुलना पर चर्चा की जाती है। केवल अहस्ताक्षरित बाइनरी कार्यान्वयन पर चर्चा की जाती है, आरएफसी (और नीचे) में SERIAL_BITS के रूप में नोट किए गए बिट्स में एक मनमाने आकार के साथ।

जोड़

अनुक्रम संख्या में एक पूर्णांक जोड़ना सरल अहस्ताक्षरित पूर्णांक जोड़ है, जिसके बाद परिणाम को वापस सीमा में लाने के लिए अहस्ताक्षरित मॉड्यूलो ऑपरेशन होता है (आमतौर पर अधिकांश आर्किटेक्चर पर अहस्ताक्षरित जोड़ में निहित होता है):

s' = (s + n) मॉड्यूलो 2^SERIAL_BITS

0 से नीचे या 2 से ऊपर का मान जोड़ना^{SERIAL_BITS−1} - 1 अपरिभाषित है। मूल रूप से, इस सीमा से परे मान जोड़ने से परिणामी अनुक्रम संख्या लपेट जाएगी, और (अक्सर) एक ऐसी संख्या उत्पन्न होगी जिसे मूल अनुक्रम संख्या से कम माना जाता है।

तुलना

दो अनुक्रम संख्याओं की तुलना करने का एक साधन i₁ और मैं₂ (अनुक्रम संख्याओं का अहस्ताक्षरित पूर्णांक निरूपण₁ और एस₂) पेश की जाती हैं।

समानता को सरल संख्यात्मक समानता के रूप में परिभाषित किया गया है।

तुलना के लिए प्रस्तुत एल्गोरिदम जटिल है, इसमें यह ध्यान रखना होगा कि क्या पहला अनुक्रम संख्या इसके मानों की सीमा के अंत के करीब है, और इस प्रकार एक छोटी लपेटी गई संख्या को वास्तव में पहले अनुक्रम संख्या से बड़ा माना जा सकता है। इस प्रकार मैं₁ को i से कम माना जाता है₂ केवल

(मैं₁ < मैं₂ और मैं₂ − मैं₁ < 2^{SERIAL_BITS−1}) या

(मैं₁ > मैं₂ और मैं₁ − मैं₂ > 2^{SERIAL_BITS−1})

कमी

RFC द्वारा प्रस्तुत एल्गोरिदम में कम से कम एक महत्वपूर्ण कमी है: ऐसे अनुक्रम संख्याएँ हैं जिनके लिए तुलना अपरिभाषित है। चूंकि कई एल्गोरिदम कई स्वतंत्र सहयोगी दलों द्वारा स्वतंत्र रूप से कार्यान्वित किए जाते हैं, ऐसी सभी स्थितियों को घटित होने से रोकना अक्सर असंभव होता है।

के लेखक RFC 1982 सामान्य समाधान प्रस्तुत किए बिना इसे स्वीकार करें: <ब्लॉककोट> जबकि परीक्षण को इस प्रकार परिभाषित करना संभव होगा कि असमानता के होते हुए भी यह आश्चर्यजनक गुण नहीं होगा मानों के सभी युग्मों के लिए परिभाषित, ऐसी परिभाषा होगी इसे लागू करना अनावश्यक रूप से बोझिल और समझने में कठिन है, और अभी भी ऐसे मामलों की अनुमति देगा जहां

s1 < s2 and (s1 + 1) > (s2 + 1)

जो बिल्कुल गैर-सहज ज्ञान युक्त है।

इस प्रकार समस्या का मामला अपरिभाषित छोड़ दिया जाता है, कार्यान्वयन स्वतंत्र है या तो परिणाम लौटाएँ, या किसी त्रुटि को चिह्नित करें, और उपयोगकर्ताओं को ध्यान रखना चाहिए किसी विशेष परिणाम पर निर्भर न रहें। आमतौर पर इसका मतलब यही होगा संख्याओं के उन विशेष युग्मों को सह-अस्तित्व में रखने की अनुमति देने से बचना। </ब्लॉककोट>

इस प्रकार, अनुक्रम संख्याओं की सभी अपरिभाषित तुलनाओं से बचना अक्सर कठिन या असंभव होता है। हालाँकि, एक अपेक्षाकृत सरल समाधान उपलब्ध है। अहस्ताक्षरित अनुक्रम संख्याओं को हस्ताक्षरित दो के पूरक अंकगणितीय संचालन पर मैप करके, किसी भी अनुक्रम संख्या की प्रत्येक तुलना को परिभाषित किया जाता है, और तुलना ऑपरेशन स्वयं नाटकीय रूप से सरल हो जाता है। आरएफसी द्वारा निर्दिष्ट सभी तुलनाएं अपने मूल सत्य मूल्यों को बरकरार रखती हैं; केवल पूर्व अपरिभाषित तुलनाएँ ही प्रभावित होती हैं।

==सामान्य समाधान== RFC  एल्गोरिदम निर्दिष्ट करता है कि, एन-बिट अनुक्रम संख्याओं के लिए, 2 हैं^N−1−1 का मान और 2 से बड़ा माना जाता है^N−1 –1 से कम माना जाता है। शेष मान के विरुद्ध तुलना (बिल्कुल 2^N−1-distant) को अपरिभाषित माना जाता है।

अधिकांश आधुनिक हार्डवेयर उपकरणों ने दो पूरक बाइनरी अंकगणितीय परिचालनों पर हस्ताक्षर किए। ये ऑपरेशन दिए गए किसी भी ऑपरेंड के मानों की पूरी श्रृंखला के लिए पूरी तरह से परिभाषित हैं, क्योंकि किसी भी एन-बिट बाइनरी संख्या में 2 हो सकते हैं^एन अलग-अलग मान, और चूंकि उनमें से एक को मान 0 द्वारा लिया जाता है, सभी गैर-शून्य सकारात्मक और नकारात्मक संख्याओं के लिए विषम संख्या में स्थान बचे हैं। वहाँ धनात्मक संख्या की तुलना में प्रतिनिधित्व करने योग्य केवल एक अधिक ऋणात्मक संख्या है। उदाहरण के लिए, 16-बिट 2 के पूरक मान में से लेकर संख्याएँ शामिल हो सकती हैं −32768 को +32767.

इसलिए, यदि हम अनुक्रम संख्याओं को 2 के पूरक पूर्णांकों के रूप में फिर से बनाते हैं और एक और अनुक्रम संख्या की अनुमति देते हैं, जिसे उससे कम माना जाता है, तो हमें तार्किक रूप से अपूर्ण के बजाय सरल हस्ताक्षरित अंकगणितीय तुलनाओं का उपयोग करने में सक्षम होना चाहिए। RFC द्वारा प्रस्तावित फॉर्मूला.

यहां कुछ उदाहरण दिए गए हैं (फिर से 16 बिट्स में), कुछ यादृच्छिक अनुक्रम संख्याओं की तुलना 0 मान वाले अनुक्रम संख्या से की जा रही है:

अहस्ताक्षरित बाइनरी हस्ताक्षरित
अनुक्रम मान दूरी
-------- ------ --------
   32767 == 0x7एफएफएफ == 32767
       1 == 0x0001 == 1
       0 == 0x0000 == 0
   65535 == 0xFFFF == −1
   65534 == 0xFFFE == −2
   32768 == 0x8000 == −32768

यह देखना आसान है कि अनुक्रम संख्याओं की हस्ताक्षरित व्याख्या सही क्रम में है, जब तक हम प्रश्न में अनुक्रम संख्या को घुमाते हैं ताकि इसका 0 उस अनुक्रम संख्या से मेल खाए जिसके साथ हम इसकी तुलना कर रहे हैं। यह पता चला है कि यह केवल एक अहस्ताक्षरित घटाव का उपयोग करके किया जाता है और परिणाम को केवल हस्ताक्षरित दो की पूरक संख्या के रूप में समझा जाता है। परिणाम दो अनुक्रम संख्याओं के बीच हस्ताक्षरित दूरी है। एक बार फिर, अगर i1 और i2 अनुक्रम संख्याओं के अहस्ताक्षरित द्विआधारी निरूपण हैं₁ और एस₂, एस से दूरी₁ से एस₂ है

distance = (signed)(i1 - i2)

यदि दूरी 0 है, तो संख्याएँ बराबर हैं। यदि यह < 0 है, तो s₁ s से कम या पहले है₂. सरल, स्वच्छ और कुशल, और पूरी तरह से परिभाषित। हालाँकि, आश्चर्य से रहित नहीं।

सभी अनुक्रम संख्या अंकगणित को अनुक्रम संख्याओं के रैपिंग से निपटना चाहिए; संख्या 2^N−1 दोनों दिशाओं में समान दूरी पर है RFC 1982 क्रम संख्या शर्तें. हमारे गणित में इन दोनों को एक दूसरे से कमतर माना जाता है:

distance1 = (signed)(0x8000 - 0x0)    == (signed)0x8000 == -32768 < 0
distance2 = (signed)(0x0    - 0x8000) == (signed)0x8000 == -32768 < 0

यह स्पष्ट रूप से किन्हीं दो अनुक्रम संख्याओं के लिए सत्य है जिनके बीच 0x8000 की दूरी है।

इसके अलावा, दो के पूरक अंकगणित का उपयोग करके सीरियल नंबर अंकगणित को लागू करने से मशीन के पूर्णांक आकार से मेल खाने वाली बिट-लंबाई के सीरियल नंबर का तात्पर्य होता है; आमतौर पर 16-बिट, 32-बिट और 64-बिट। 20-बिट सीरियल नंबरों को लागू करने के लिए बदलाव की आवश्यकता है (32-बिट इनट्स मानकर):

distance = (signed)((i1 << 12) - (i2 << 12))

यह भी देखें

• तारीख विंडोिंग
• लॉलीपॉप अनुक्रम क्रमांकन
• मॉड्यूलर अंकगणित

बाहरी संबंध

• RFC 2182
• RFC 1982