Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бинарлық сандық жүйелерде теріс сандарды кодтау
Encoding of negative numbers in binary number systems
Есептеу техникасында, бинарлық сандық жүйелерде теріс сандарды кодтау үшін қол қойылған сандық өрнектемелер қажет. Математикада, кез келген сан негізіндегі теріс сандар минус белгісімен ("−") басында көрсетіледі. Дегенмен, RAM немесе CPU тіркемелерінде сандар тек биттер тізбегі түрінде бейнеленеді, қосымша символдарсыз. Бинарлық сандық жүйені қол қойылған сандарды көрсету үшін кеңейтудің ең белгілі төрт әдісі: белгі-мөлшері, біртінші толықтыру, екілік толықтыру және смещенный бинарлық. Кейбір балама әдістерде ашық белгілердің орнына жасырын белгілер қолданылады, мысалы, теріс екілік, −2 негізін пайдаланады. Оң, теріс, бөлшектік немесе осы тақырыптарға қатысты басқа да түрлендірулер үшін басқа негіздерге де сәйкес әдістерді құруға болады. Кез келген өрнектемелердің қайсысының жалпылама артық екенін анықтайтын нақты критерий жоқ. Бүтін сандар үшін, қазіргі есептеу құрылғыларының көпшілігінде екілік толықтыру қолданылады, бірақ Unisys ClearPath Dorado сериялы серверлері біртінші толықтыруды пайдаланады.
In computing, signed number representations are required to encode negative numbers in binary number systems. In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU registers, numbers are represented only as sequences of bits, without extra symbols. The four best known methods of extending the binary numeral system to represent signed numbers are: sign–magnitude, ones' complement, two's complement, and offset binary. Some of the alternative methods use implicit instead of explicit signs, such as negative binary, using the base −2. Corresponding methods can be devised for other bases, whether positive, negative, fractional, or other elaborations on such themes. There is no definitive criterion by which any of the representations is universally superior. For integers, the representation used in most current computing devices is two's complement, although the Unisys ClearPath Dorado series mainframes use ones' complement.
Тарих
Цифрлық есептеудің алғашқы күндері аппараттық технология және математикалық технология (номерлеу жүйелері) бойынша бәсекелес идеялармен ерекшеленді. Басты пікірталастардың бірі теріс сандардың форматы болды, сол дәуірдегі жетекші сарапшылардың көптегені өте қатаң және әртүрлі пікірлер білдірді. Бір топ екілік толықтыруды қолдады – бүгінде басым жүйе. Тағы бір топ бірлік толықтыруды қолдады, онда теріс мән оның оң мәніндегі барлық биттерді инверсиялау арқылы құралады. Үшінші топ белгі-шама жүйесін қолдады, онда мән оңнан теріске қарапайым түрде сөздің ең жоғары ретті бітін ауыстыру арқылы өзгереді. Әрбір жүйе үшін жақтастар мен қарсыластар болды. Белгі-шама жүйесі 1960 жылдары кең таралған процесс болған жадтың құлағандарын (memory dumps) оңай іздеуге мүмкіндік берді, себебі кішкентай сандық мәндерде 1 биттердің саны аз болды. Бұл жүйелер ішкі түрде бірлік толықтыру арқылы есептеулер жүргізді, сондықтан сандар тізілімнен математикалық процессорға жіберілгенде бірлік толықтыру мәндеріне айналдырылып, нәтиже тізілімге қайтарылғанда қайтадан белгі-шамаға түрлендірілуі керек еді. Бұл жүйелерге басқа жүйелерге қарағанда көбірек логикалық элементтер (gates) қажет болды, бұл дискретті транзисторлардың құны мен орналастыруы маңызды болған кезде үлкен мәселе болып табылды. IBM осы жүйенің ерте жақтастарының бірі болды, олардың 704, 709 және 709x сериялы компьютерлері оны қолдануда ең танымал жүйелердің бірі болды. Бірлік толықтыру аппараттық құрылымды біршама қарапайым етуге мүмкіндік берді, себебі математикалық процессорға және одан мәндерді түрлендірудің қажеті болмады. Бірақ ол белгі-шама жүйесімен бірге жағымсыз ерекшелікті де бөлісті: теріс нөлді (-0) бейнелеу мүмкіндігі. Теріс нөл оң нөл сияқты әрекет етеді: есептеуде операнд ретінде қолданылғанда, операнд оң немесе теріс нөл болса да нәтиже бірдей болады. Бұл кемшілік, бір мәннің екі түрінің болуы нөлге теңдігін тексеру кезінде екі салыстыруды талап етеді. Бірлік толықтыру арқылы алу (borrow) операциясы да болуы мүмкін (төменде сипатталған). Бұл қосу және алу логикасын күрделендіреді, немесе керісінше, оны қарапайым етеді, себебі алу үшін екінші операндтың биттерін қосушыға жібергенде инверсиялау жеткілікті. PDP 1, CDC 160 сериясы, CDC 3000 сериясы, CDC 6000 сериясы, UNIVAC 1100 сериясы және LINC компьютері бірлік толықтыруын қолданды. Екілік толықтыру аппараттық құрылымда іске асыру үшін ең оңайы болып табылады, бұл оның кең таралған танымалдылығының басты себебі болуы мүмкін. Алғашқы мейнфреймдердегі процессорлар көбінесе мыңдаған транзисторлардан тұрды, сондықтан транзисторлардың маңызды бөлігін жою үлкен үнемдеуге әкелді. IBM System/360, GE 600 сериясы, PDP 6 және PDP 10 сияқты мейнфреймдер, сондай-ақ PDP 5 және PDP 8, PDP 11 және VAX машиналары сияқты миникомпьютерлер екілік толықтыруды қолданды. Алғашқы интегралды схемаларға негізделген процессорлардың (Intel 8080 және т.б.) архитекторлары да екілік толықтыруды таңдады. Интегралды схемалар технологиясы дамыған сайын, екілік толықтыру технологиясы барлық процессорларда қабылданды, соның ішінде x86, m68k, Power ISA, MIPS, SPARC, ARM, Itanium, PA RISC және DEC Alpha.
The early days of digital computing were marked by competing ideas about both hardware technology and mathematics technology (numbering systems). One of the great debates was the format of negative numbers, with some of the era's top experts expressing very strong and differing opinions. One camp supported two's complement, the system that is dominant today. Another camp supported ones' complement, where a negative value is formed by inverting all of the bits in its positive equivalent. A third group supported sign–magnitude, where a value is changed from positive to negative simply by toggling the word's highest order bit. There were arguments for and against each of the systems. Sign–magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 bits. These systems did ones' complement math internally, so numbers would have to be converted to ones' complement values when they were transmitted from a register to the math unit and then converted back to sign–magnitude when the result was transmitted back to the register. The electronics required more gates than the other systemsa key concern when the cost and packaging of discrete transistors were critical. IBM was one of the early supporters of sign–magnitude, with their 704, 709 and 709x series computers being perhaps the best known systems to use it. Ones' complement allowed for somewhat simpler hardware designs, as there was no need to convert values when passed to and from the math unit. But it also shared an undesirable characteristic with sign–magnitude: the ability to represent negative zero (−0). Negative zero behaves exactly like positive zero: when used as an operand in any calculation, the result will be the same whether an operand is positive or negative zero. The disadvantage is that the existence of two forms of the same value necessitates two comparisons when checking for equality with zero. Ones' complement subtraction can also result in an end around borrow (described below). It can be argued that this makes the addition and subtraction logic more complicated or that it makes it simpler, as a subtraction requires simply inverting the bits of the second operand as it is passed to the adder. The PDP 1, CDC 160 series, CDC 3000 series, CDC 6000 series, UNIVAC 1100 series, and LINC computer use ones' complement representation. Two's complement is the easiest to implement in hardware, which may be the ultimate reason for its widespread popularity. Processors on the early mainframes often consisted of thousands of transistors, so eliminating a significant number of transistors was a significant cost savings. Mainframes such as the IBM System/360, the GE 600 series, and the PDP 6 and PDP 10 use two's complement, as did minicomputers such as the PDP 5 and PDP 8 and the PDP 11 and VAX machines. The architects of the early integrated circuit based CPUs (Intel 8080, etc.) also chose to use two's complement math. As IC technology advanced, two's complement technology was adopted in virtually all processors, including x86, m68k, Power ISA, MIPS, SPARC, ARM, Itanium, PA RISC, and DEC Alpha.
Басқа жүйелер
Google протоколының буферлеріндегі "зигзаг кодтау" – бұл таңбалы санға ұқсас жүйе, бірақ таңбаны көрсету үшін ең кіші мәнді бит қолданылады және нөлдің бір ғана өрнегі бар. Бұл теріс емес (белгісіз) бүтін сандарға арналған өзгермелі ұзындығы сандық кодтауды, белгілі бүтін сандар үшін тиімді пайдалануға мүмкіндік береді. Осыған ұқсас әдіс, Advanced Video Coding/H.264 және High Efficiency Video Coding/H.265 видеоқысу стандарттарында экспоненциалдық Голомб кодтауын теріс сандарға дейін кеңейту үшін қолданылады. Бұл кеңейтуде ең кіші мәнді бит, дерлік таңба биті болып табылады; нөлдің ең кіші мәнді биті (0), барлық теріс сандардың ең кіші мәнді битімен бірдей. Бұл таңдаудың нәтижесінде, ең үлкен шамадағы оң сан, ең үлкен шамадағы теріс саннан бірге артық болады, екілік толықтырудан немесе Google протоколының зигзаг кодтауынан өзгеше. Тағы бір тәсіл – әр цифрға таңба тағайындау, яғни таңбалы цифрлық өрнектерді қолдану. Мысалы, 1726 жылы Джон Колсон өрнектерді "кіші сандарға" – 1, 2, 3, 4 және 5 сандарына дейін азайтуды ұсынды. 1840 жылы Огюстен Коши есептеулердегі қателерді азайту үшін мұндай өзгертілген ондық сандарды қолдануды жөн көретінін айтты.
Google's Protocol Buffers "zig zag encoding" is a system similar to sign–magnitude, but uses the least significant bit to represent the sign and has a single representation of zero. This allows a variable length quantity encoding intended for nonnegative (unsigned) integers to be used efficiently for signed integers. A similar method is used in the Advanced Video Coding/H.264 and High Efficiency Video Coding/H.265 video compression standards to extend exponential Golomb coding to negative numbers. In that extension, the least significant bit is almost a sign bit; zero has the same least significant bit (0) as all the negative numbers. This choice results in the largest magnitude representable positive number being one higher than the largest magnitude negative number, unlike in two's complement or the Protocol Buffers zig zag encoding. Another approach is to give each digit a sign, yielding the signed digit representation. For instance, in 1726, John Colson advocated reducing expressions to "small numbers", numerals 1, 2, 3, 4, and 5. In 1840, Augustin Cauchy also expressed preference for such modified decimal numbers to reduce errors in computation.