Misplaced Pages

#200799

38-496: Six-bit Transcode looked backward to older systems; USASCII with 128 characters and EBCDIC with 256 characters looked forward. Transcode disappeared very quickly but the EBCDIC and USASCII dialects of Bisync continued in use. At one time Bisync was the most widely used communications protocol and is still in limited use in 2013. Bisync differs from protocols that succeeded it in the complexity of message framing. Later protocols use

76-449: A Hamming space ), as it fulfills the conditions of non-negativity, symmetry, the Hamming distance of two words is 0 if and only if the two words are identical, and it satisfies the triangle inequality as well: Indeed, if we fix three words a , b and c , then whenever there is a difference between the i th letter of a and the i th letter of c , then there must be a difference between

114-404: A finite field . The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different. The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the Hamming distance between: For a fixed length n , the Hamming distance is a metric on the set of the words of length n (also known as

152-549: A hypercube graph . One can also view a binary string of length n as a vector in R n {\displaystyle \mathbb {R} ^{n}} by treating each symbol in the string as a real coordinate; with this embedding, the strings form the vertices of an n -dimensional hypercube , and the Hamming distance of the strings is equivalent to the Manhattan distance between the vertices. The minimum Hamming distance or minimum distance (usually denoted by d min )

190-472: A "space compression" option. Transcode is a six-bit character code . It relates to IBM's punched card code but, like EBCDIC , it is not BCD . Its 64 values consist of the 26 uppercase letters, 10 numbers, 11 symbols, space , and 16 control characters . Its 48 printable characters are ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 .'-/@#$ %&*⌑ ; it cannot represent ,:;!?"()[]<>+^=_\`{}|~ . Characters are transmitted with odd parity . The 2780 cannot use

228-432: A 2-wire environment, this causes a noticeable round-trip delay and reduces performance. Some datasets support full-duplex operation, and full-duplex (4-wire) can be used in many circumstances to improve performance by eliminating the turn-around time, at the added expense of 4-wire installation and support. In typical full-duplex, data packets are transmitted along one wire pair while the acknowledgements are returned along

266-527: A DLE character to indicate their control significance (The DLE character itself is represented by the sequence DLE DLE). This technique became known as character stuffing , by analogy with bit stuffing . The link control protocol is similar to STR. The designers attempted to protect against simple transmission errors. The protocol requires that every message be acknowledged (ACK0/ACK1) or negatively acknowledged (NAK), so transmission of small packets has high transmission overhead. The protocol can recover from

304-440: A corrupted data frame, a lost data frame, and a lost acknowledgment. Error recovery is by retransmission of the corrupted frame. Since Bisync data packets are not serial-numbered, it's considered possible for a data frame to go missing without the receiver realizing it. Therefore, alternating ACK0s and ACK1s are deployed; if the transmitter receives the wrong ACK, it can assume a data packet (or an ACK) went missing. A potential flaw

342-534: A few years, one of the three character sets used by IBM for Binary Synchronous Communications . Transmission using 6-bit Transcode had higher throughput than transmission using 8-bit EBCDIC or ASCII, provided that the data to be transmitted used a limited set of 48 characters. The IBM 2780 data transmission terminal was announced with Transcode support in 1967. Its successor, the IBM 3780 data communication terminal, announced in 1972, dropped Transcode support and added

380-907: A fixed-length binary word as an estimate of error, and therefore is sometimes called the signal distance . For q -ary strings over an alphabet of size q  ≥ 2 the Hamming distance is applied in case of the q-ary symmetric channel , while the Lee distance is used for phase-shift keying or more generally channels susceptible to synchronization errors because the Lee distance accounts for errors of ±1. If q = 2 {\displaystyle q=2} or q = 3 {\displaystyle q=3} both distances coincide because any pair of elements from Z / 2 Z {\textstyle \mathbb {Z} /2\mathbb {Z} } or Z / 3 Z {\textstyle \mathbb {Z} /3\mathbb {Z} } differ by 1, but

418-405: A mid-1990 BSC was replaced by the X.25 infrastructure. Some important systems use Bisync data framing with a different link control protocol. Houston Automatic Spooling Priority (HASP) uses Bisync half-duplex hardware in conjunction with its own link control protocol to provide full-duplex multi-datastream communication between a small computer and a mainframe running HASP. In Bisync terms, this

SECTION 10

#1732852589201

456-526: A single framing scheme for all messages sent by the protocol. HDLC , Digital Data Communications Message Protocol (DDCMP), Point-to-Point Protocol (PPP), etc. each have different framing schemes but only one frame format exists within a specific protocol. Bisync has five different framing formats. ACK0 and ACK1 (even/odd affirmative acknowledgement) are encoded as two characters—DLE '70'x, and DLE / for EBCDIC, DLE 0 and DLE 1 for USASCII, DLE - and DLE T for Transcode. WABT (wait before transmit)

494-513: Is conversational mode . Some early X.25 networks tolerated a connection scheme where transparent Bisync data frames encapsulated HDLC LAPB data and control packets. As of 2012, several vendors encapsulate Bisync transmissions within TCP/IP data streams. Bisync began to be displaced in the 1970s by Systems Network Architecture (SNA) which allows construction of a network with multiple hosts and multiple programs using telecommunications. X.25 and

532-408: Is k =2 error detecting. This means that if one bit is flipped or two bits are flipped, the error can be detected. If three bits are flipped, then "000" becomes "111" and the error cannot be detected. A code C is said to be k-error correcting if, for every word w in the underlying Hamming space H , there exists at most one codeword c (from C ) such that the Hamming distance between w and c

570-431: Is also a SYN, character synchronization has been achieved. The receiver then searches for a character that can start a frame. Characters outside of this set are described as "leading graphics". They are sometimes used to identify the sender of a frame. Long messages have SYN bytes inserted approximately every second to maintain synchronization. These are ignored by the receiver. A normal block ending character (ETB or ETX)

608-533: Is at most k . In other words, a code is k -errors correcting if the minimum Hamming distance between any two of its codewords is at least 2 k +1. This is also understood geometrically as any closed balls of radius k centered on distinct codewords being disjoint. These balls are also called Hamming spheres in this context. For example, consider the same 3-bit code consisting of the two codewords "000" and "111". The Hamming space consists of 8 words 000, 001, 010, 011, 100, 101, 110 and 111. The codeword "000" and

646-416: Is followed by a check sum (block check character or BCC). For USASCII, this is a one character longitudinal redundancy check (LRC); for Transcode and EBCDIC, the check sum is a two character cyclic redundancy check (CRC). A data frame may contain an intermediate check sum preceded by an ITB character. This ability to include intermediate check sums in a long data frame allows a considerable improvement of

684-452: Is part of the initial Bisync protocol. A master station, normally a computer, can sequentially poll terminals which are attached via analog bridges to the same communication line. This is accomplished by sending a message consisting only of an ENQ character addressed to each device in turn. The selected station then transmits a message to the master or reply with EOT to indicate that it has no data to transmit. The original purpose of Bisync

722-431: Is that corruption of ACK0 into ACK1 could result in duplication of a data frame. Error protection for ACK0 and ACK1 is weak. The Hamming distance between the two messages is only two bits. The protocol is half-duplex (2-wire). In this environment, packets or frames of transmission are strictly unidirectional, necessitating 'turn-around' for even the simplest purposes, such as acknowledgments. Turn-around involves In

760-419: Is used to define some essential notions in coding theory , such as error detecting and error correcting codes . In particular, a code C is said to be k error detecting if, and only if, the minimum Hamming distance between any two of its codewords is at least k +1. For example, consider a code consisting of two codewords "000" and "111". The Hamming distance between these two words is 3, and therefore it

798-657: The Internet Protocol are later protocols which, like SNA, provide more than mere link control. A large number of devices use the Bisync protocol, some of these are: Other computer vendors offered their own variety of byte-oriented protocols similar to Bisync. Some widely used protocols include Digital Equipment Corporation 's Digital Data Communications Message Protocol , and Burroughs Corporation 's Poll and Select Protocol . Transcode (character encoding) Six-Bit Transcode , or Six-Bit Transmission Code , was, for

SECTION 20

#1732852589201

836-463: The i th letter of a and i th letter of b , or between the i th letter of b and the i th letter of c . Hence the Hamming distance between a and c is not larger than the sum of the Hamming distances between a and b and between b and c . The Hamming distance between two words a and b can also be seen as the Hamming weight of a − b for an appropriate choice of the − operator, much as

874-406: The zip() function merges two equal-length collections in pairs. The following C function will compute the Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The running time of this procedure is proportional to the Hamming distance rather than to the number of bits in the inputs. It computes the bitwise exclusive or of the two inputs, and then finds

912-452: The 16 control characters as data characters in Transcode mode. Hamming distance In information theory , the Hamming distance between two strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or equivalently,

950-408: The Hamming distance between "000" and "111" is 3, and those comprise the entire set of codewords in the code, the minimum Hamming distance is 3, which satisfies 2k+1 = 3 . Thus a code with minimum Hamming distance d between its codewords can detect at most d -1 errors and can correct ⌊( d -1)/2⌋ errors. The latter number is also called the packing radius or the error-correcting capability of

988-513: The Hamming distance between two strings: Or, in a shorter expression: The function hamming_distance() , implemented in Python 3 , computes the Hamming distance between two strings (or other iterable objects) of equal length by creating a sequence of Boolean values indicating mismatches and matches between corresponding positions in the two inputs, then summing the sequence with True and False values, interpreted as one and zero, respectively. where

1026-933: The System/360 era, these access methods were BTAM (Basic Telecommunications Access Method) and QTAM (Queued Telecommunications Access Method) – which was later replaced by Telecommunications Access Method (TCAM). IBM introduced VTAM (Virtual Telecommunications Access Method) with the System/370 . Teleprocessing monitors such as IBM's CICS and third-party software such as Remote DUCS (display unit control system) and Westi platforms used Bisync line control to communicate with remote devices. The academic computing network Bitnet , together with connecting networks in other geographic areas, used Bisync to connect 3000 computer systems at its peak. Financial network S.W.I.F.T. used BSC protocol for communication between Regional Center and Institution (bank) server over leased line. In

1064-564: The above or a SYN. An optional heading containing control information can precede data in a frame. The content of the heading is not defined by the protocol but is defined for each specific device. The heading, if present, is preceded by an SOH (start of heading) character and followed by an STX (start of text). Text data normally follows the heading, begun by the STX, and terminated by ETX (end of text) or ETB (end transmission block). Normal data frames do not allow certain characters to appear in

1102-403: The code. The Hamming distance is named after Richard Hamming , who introduced the concept in his fundamental paper on Hamming codes , Error detecting and error correcting codes , in 1950. Hamming weight analysis of bits is used in several disciplines including information theory , coding theory , and cryptography . It is used in telecommunication to count the number of flipped bits in

1140-459: The data. These are the block ending characters: ETB, ETX and ENQ and the ITB and SYN characters. The number of unique characters that can be transmitted is therefore limited to 59 for Transcode, 123 for USASCII, or 251 for EBCDIC. Transparent data framing provides an unrestricted alphabet of 64, 128 or 256 characters. In transparent mode block framing characters such as ETB, ETX, and SYN are preceded by

1178-402: The difference between two integers can be seen as a distance from zero on the number line. For binary strings a and b the Hamming distance is equal to the number of ones ( population count ) in a XOR b . The metric space of length- n binary strings, with the Hamming distance, is known as the Hamming cube ; it is equivalent as a metric space to the set of distances between vertices in

Binary Synchronous Communications - Misplaced Pages Continue

1216-560: The distances are different for larger q {\displaystyle q} . The Hamming distance is also used in systematics as a measure of genetic distance. However, for comparing strings of different lengths, or strings where not just substitutions but also insertions or deletions have to be expected, a more sophisticated metric like the Levenshtein distance is more appropriate. The following function, written in Python 3, returns

1254-466: The error detection probability. USASCII characters are also transmitted using odd parity for additional checking. Pad characters are required following a line turn-around—NAK, EOT, ENQ, ACK0, ACK1. If the transmission ends with EOT or ETX the pad follows the BCC. This pad is either all '1' bits or alternating '0' and '1' bits. The next transmission begins with a pad character which can be either of

1292-474: The minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming . A major application is in coding theory , more specifically to block codes , in which the equal-length strings are vectors over

1330-417: The other. Much Bisync traffic is point-to-point . Point-to-point lines can optionally use contention to determine the master station. In this case one device can transmit ENQ to bid for control. The other device can reply ACK0 to accept the bid and prepare to receive, or NAK or WABT to refuse. In some cases connection of a terminal to multiple hosts is possible via the dial telephone network. Multi-drop

1368-400: The single bit error words "001","010","100" are all less than or equal to the Hamming distance of 1 to "000". Likewise, codeword "111" and its single bit error words "110","101" and "011" are all within 1 Hamming distance of the original "111". In this code, a single bit error is always within 1 Hamming distance of the original codes, and the code can be 1-error correcting , that is k=1 . Since

1406-459: Was encoded as DLE ", DLE ?, or DLE W. All frame formats begin with at least two SYN bytes . The binary form of the SYN byte has the property that no rotation of the byte is equal to the original. This allows the receiver to find the beginning of a frame by searching the received bit stream for the SYN pattern. When this is found, tentative byte synchronization has been achieved. If the next character

1444-562: Was for batch communications between a System/360 mainframe and another mainframe or a Remote Job Entry (RJE) terminal such as the IBM 2780 or IBM 3780 . The RJE terminals support a limited number of data formats: punched card images in and out and print line images to the terminal. Some non-IBM hardware vendors such as Mohawk Data Sciences used Bisync for other purposes such as tape-to-tape transmission. A programmer can easily emulate an RJE terminal or other device. IBM offered assembler language macros to provide programming support. During

#200799