String (computer science)
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed. A string is considered a data type and is implemented as an array data structure of bytes that stores a sequence of elements characters, using some character encoding. String may denote more general arrays or other sequence data types and structures. Depending on programming language and precise data type used, a variable declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ dynamic allocation to allow it to hold a variable number of elements; when a string appears in source code, it is known as a string literal or an anonymous string. In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set called an alphabet. Let Σ be a non-empty finite set of symbols, called the alphabet.
No assumption is made about the nature of the symbols. A string over Σ is any finite sequence of symbols from Σ. For example, if Σ = 01011 is a string over Σ; the length of a string s can be any non-negative integer. The empty string is the unique string over Σ of length 0, is denoted ε or λ; the set of all strings over Σ of length n is denoted Σn. For example, if Σ = Σ2 =. Note that Σ0 = for any alphabet Σ; the set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn, Σ ∗ = ⋃ n ∈ N ∪ Σ n For example, if Σ = Σ* =. Although the set Σ* itself is countably infinite, each element of Σ* is a string of finite length. A set of strings over Σ is called a formal language over Σ. For example, if Σ =, the set of strings with an number of zeros, is a formal language over Σ. Concatenation is an important binary operation on Σ*. For any two strings s and t in Σ*, their concatenation is defined as the sequence of symbols in s followed by the sequence of characters in t, is denoted st.
For example, if Σ =, s = bear, t = hug st = bearhug and ts = hugbear. String concatenation is an non-commutative operation; the empty string ε serves as the identity element. Therefore, the set Σ* and the concatenation operation form a monoid, the free monoid generated by Σ. In addition, the length function defines a monoid homomorphism from Σ* to the non-negative integers. A string s is said to be a substring or factor of t if there exist strings u and v such that t = usv; the relation "is a substring of" defines a partial order on Σ*, the least element of, the empty string. A string s is said to be a prefix of t if there exists a string u such that t = su. If u is nonempty, s is said to be a proper prefix of t. Symmetrically, a string s is said to be a suffix of t if there exists a string u such that t = us. If u is nonempty, s is said to be a proper suffix of t. Suffixes and prefixes are substrings of t. Both the relations "is a prefix of" and "is a suffix of" are prefix orders. A string s = uv.
For example, if Σ = the string 0011001 is a rotation of 0100110, where u = 00110 and v = 01. The reverse of a string is a string in reverse order. For example, if s = abc the reverse of s is cba. A string, the reverse of itself is called a palindrome, which includes the empty string and all strings of length 1, it is useful to define an ordering on a set of strings. If the alphabet Σ has a total order one can define a total order on Σ* called lexicographical order. For example, if Σ = and 0 < 1 the lexicographical order on Σ* includes the relationships ε < 0 < 00 < 000 <... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111... The lexicographical order is total if the alphabetical order is, but isn't well-founded for any nontrivial alphabet if the alphabetical order is. See Shortlex for an alternative string ordering that preserves well-foundedness. A number of additional operations on strings occur in the formal theory; these are given in the article on string operations.
Strings admit the following interpretation as nodes on a graph: Fixed-length strings can be viewed as nodes on a hypercube Variable-length strings can be viewed as nodes on the k-ary tree, where k is the number of symbols in Σ Infinite strings can be viewed as i
A digital signal is a signal, being used to represent data as a sequence of discrete values. This contrasts with an analog signal. Simple digital signals represent information in discrete bands of analog levels. All levels within a band of values represent the same information state. In most digital circuits, the signal can have two possible values, they are represented by two voltage bands: one near a reference value, the other a value near the supply voltage. These correspond to the two values "zero" and "one" of the Boolean domain, so at any given time a binary signal represents one binary digit; because of this discretization small changes to the analog signal levels do not leave the discrete envelope, as a result are ignored by signal state sensing circuitry. As a result, digital signals have noise immunity. Digital signals having more than two states are used. For example, signals that can assume three possible states are called three-valued logic. In a digital signal, the physical quantity representing the information may be a variable electric current or voltage, the intensity, phase or polarization of an optical or other electromagnetic field, acoustic pressure, the magnetization of a magnetic storage media, etcetera.
Digital signals are used in all digital electronics, notably computing equipment and data transmission. The term digital signal has related definitions in different contexts. In digital electronics a digital signal is a pulse train, i.e. a sequence of fixed-width square-wave electrical pulses or light pulses, each occupying one of a discrete number of levels of amplitude. A special case is a logic signal or a binary signal, which varies between a low and a high signal level. In digital signal processing, a digital signal is a representation of a physical signal, a sampled and quantized. A digital signal is an abstraction, discrete in time and amplitude; the signal's value only exists at regular time intervals, since only the values of the corresponding physical signal at those sampled moments are significant for further digital processing. The digital signal is a sequence of codes drawn from a finite set of values; the digital signal may be stored, processed or transmitted physically as a pulse-code modulation signal.
In digital communications, a digital signal is a continuous-time physical signal, alternating between a discrete number of waveforms, representing a bitstream. The shape of the waveform depends the transmission scheme, which may be either a line coding scheme allowing baseband transmission; such a carrier-modulated sine wave is considered a digital signal in literature on digital communications and data transmission, but considered as a bitstream converted to an analog signal in electronics and computer networking. In communications, sources of interference are present, noise is a significant problem; the effects of interference are minimized by filtering off interfering signals as much as possible and by using data redundancy. The main advantages of digital signals for communications are considered to be the noise immunity to noise capability, the ability, in many cases such as with audio and video data, to use data compression to decrease the bandwidth, required on the communication media.
A waveform that switches representing the two states of a Boolean value is referred to as a digital signal or logic signal or binary signal when it is interpreted in terms of only two possible digits. The two states are represented by some measurement of an electrical property: Voltage is the most common, but current is used in some logic families. A threshold is designed for each logic family; when below that threshold, the signal is low. The clock signal is a special digital signal, used to synchronize many digital circuits; the image shown can be considered the waveform of a clock signal. Logic changes are triggered either by the falling edge; the rising edge is the transition from a low voltage to a high voltage. The falling edge is the transition from a high voltage to a low one. Although in a simplified and idealized model of a digital circuit, we may wish for these transitions to occur instantaneously, no real world circuit is purely resistive and therefore no circuit can change voltage levels.
This means that during a short, finite transition time the output may not properly reflect the input, will not correspond to either a logically high or low voltage. To create a digital signal, an analog signal must be modulated with a control signal to produce it; the simplest modulation, a type of unipolar encoding, is to switch on and off a DC signal, so that high voltages represent a'1' and low voltages are'0'. In digital radio schemes one or more carrier waves are amplitude, frequency or phase modulated by the control signal to produce a digital signal suitable for transmission. Asymmetric Digital Subscriber Line over telephone wires, does not use binary logic.
The T-carrier is a member of the series of carrier systems developed by AT&T Bell Laboratories for digital transmission of multiplexed telephone calls. The first version, the Transmission System 1, was introduced in 1962 in the Bell System, could transmit up to 24 telephone calls over a single transmission line of copper wire. Subsequent specifications carried multiples of the basic T1 data rates, such as T2 with 96 channels, T3 with 672 channels, others; the T-carrier is a hardware specification for carrying multiple time-division multiplexed telecommunications channels over a single four-wire transmission circuit. It was developed by AT&T at Bell Laboratories ca. 1957 and first employed by 1962 for long-haul pulse-code modulation digital voice transmission with the D1 channel bank. The T-carriers are used for trunking between switching centers in a telephone network, including to private branch exchange interconnect points, it uses the same twisted pair copper wire that analog trunks used, employing one pair for transmitting, another pair for receiving.
Signal repeaters may be used for extended distance requirements. Before the digital T-carrier system, carrier wave systems such as 12-channel carrier systems worked by frequency division multiplexing. A T1 trunk could transmit 24 telephone calls at a time, because it used a digital carrier signal called Digital Signal 1. DS-1 is a communications protocol for multiplexing the bitstreams of up to 24 telephone calls, along with two special bits: a framing bit and a maintenance-signaling bit. T1's maximum data transmission rate is 1.544 megabits per second. Europe and most of the rest of the world, except Japan, have standardized the E-carrier system, a similar transmission system with higher capacity, not directly compatible with the T-carrier. Existing frequency-division multiplexing carrier systems worked well for connections between distant cities, but required expensive modulators and filters for every voice channel. For connections within metropolitan areas, Bell Labs in the late 1950s sought cheaper terminal equipment.
Pulse-code modulation allowed sharing a coder and decoder among several voice trunks, so this method was chosen for the T1 system introduced into local use in 1961. In decades, the cost of digital electronics declined to the point that an individual codec per voice channel became commonplace, but by the other advantages of digital transmission had become entrenched; the most common legacy of this system is the line rate speeds. "T1" now means any data circuit line rate. The T1 format carried 24 pulse-code modulated, time-division multiplexed speech signals each encoded in 64 kbit/s streams, leaving 8 kbit/s of framing information which facilitates the synchronization and demultiplexing at the receiver; the T2 and T3 circuit channels carry multiple T1 channels multiplexed, resulting in transmission rates of 6.312 and 44.736 Mbit/s, respectively. A T3 line comprises each operating at total signaling rate of 1.544 Mbit/s. It is possible to get a fractional T3 line, meaning a T3 line with some of the 28 lines turned off, resulting in a slower transfer rate but at reduced cost.
The 1.544 Mbit/s rate was chosen because tests done by AT&T Long Lines in Chicago were conducted underground. The test site was typical of Bell System outside plant of the time in that, to accommodate loading coils, cable vault manholes were physically 2,000 meters apart, which determined the repeater spacing; the optimum bit rate was chosen empirically—the capacity was increased until the failure rate was unacceptable reduced to leave a margin. Companding allowed acceptable audio performance with only seven bits per PCM sample in this original T1/D1 system; the D3 and D4 channel banks had an extended frame format, allowing eight bits per sample, reduced to seven every sixth sample or frame when one bit was "robbed" for signaling the state of the channel. The standard does not allow an all zero sample which would produce a long string of binary zeros and cause the repeaters to lose bit sync. However, when carrying data there could be long strings of zeros, so one bit per sample is set to "1" leaving 7 bits × 8,000 frames per second for data.
A more detailed understanding of how the rate of 1.544 Mbit/s was divided into channels is as follows. Given that the telephone system nominal voiceband is 4,000 Hz, the required digital sampling rate is 8,000 Hz. Since each T1 frame contains 1 byte of voice data for each of the 24 channels, that system needs 8,000 frames per second to maintain those 24 simultaneous voice channels; because each frame of a T1 is 193 bits in length, 8,000 frames per second is multiplied by 193 bits to yield a transfer rate of 1.544 Mbit/s. T1 used Alternate Mark Inversion to reduce frequency bandwidth and eliminate the DC component of the signal. B8ZS became common practice. For AMI, each mark pulse had the opposite polarity of the previous one and each space was at a level of zero, resulting in a three level signal which however only carried binary data. Similar British 23 channel systems at 1.536 megabaud in the 1970s were equipped with ternary signal repeaters, in anticipation of using a 3B2T or 4B3T code to increase the number of voice channels in future, but in the 1980s the systems were replaced with European standard ones.
In telecommunications, transmission is the process of sending and propagating an analogue or digital information signal over a physical point-to-point or point-to-multipoint transmission medium, either wired, optical fiber or wireless. One example of transmission is the sending of a signal with limited duration, for example a block or packet of data, a phone call, or an email. Transmission technologies and schemes refer to physical layer protocol duties such as modulation, line coding, error control, bit synchronization and multiplexing, but the term may involve higher-layer protocol duties, for example, digitizing an analog message signal, data compression. Transmission of a digital message, or of a digitized analog signal, is known as digital communication
Synchronization is the coordination of events to operate a system in unison. The conductor of an orchestra keeps the orchestra synchronized or in time. Systems that operate with all parts in synchrony are said to be synchronous or in sync—and those that are not are asynchronous. Today, time synchronization can occur between systems around the world through satellite navigation signals. Time-keeping and synchronization of clocks has been a critical problem in long-distance ocean navigation. Before radio navigation and satellite-based navigation, navigators required accurate time in conjunction with astronomical observations to determine how far east or west their vessel traveled; the invention of an accurate marine chronometer revolutionized marine navigation. By the end of the 19th century, important ports provided time signals in the form of a signal gun, flag, or dropping time ball so that mariners could check their chronometers for error. Synchronization was important in the operation of 19th century railways, these being the first major means of transport fast enough for differences in local time between adjacent towns to be noticeable.
Each line handled the problem by synchronizing all its stations to headquarters as a standard railroad time. In some territories, sharing of single railroad tracks was controlled by the timetable; the need for strict timekeeping led the companies to settle on one standard, civil authorities abandoned local mean solar time in favor of that standard. In electrical engineering terms, for digital logic and data transfer, a synchronous circuit requires a clock signal. However, the use of the word "clock" in this sense is different from the typical sense of a clock as a device that keeps track of time-of-day. In a different sense, electronic systems are sometimes synchronized to make events at points far apart appear simultaneous or near-simultaneous from a certain perspective. Timekeeping technologies such as the GPS satellites and Network Time Protocol provide real-time access to a close approximation to the UTC timescale and are used for many terrestrial synchronization applications of this kind.
Synchronization is an important concept in the following fields: Computer science Cryptography Multimedia Music Neuroscience Photography Physics Synthesizers Telecommunication Synchronization of multiple interacting dynamical systems can occur when the systems are autonomous oscillators. For instance, integrate-and-fire oscillators with either two-way or one-way coupling can synchronize when the strength of the coupling is greater than the differences among the free-running natural oscillator frequencies. Poincare phase oscillators are model systems that can interact and synchronize within random or regular networks. In the case of global synchronization of phase oscillators, an abrupt transition from unsynchronized to full synchronization takes place when the coupling strength exceeds a critical threshold; this is known as the Kuramoto model phase transition. Synchronization is an emergent property that occurs in a broad range of dynamical systems, including neural signaling, the beating of the heart and the synchronization of fire-fly light waves.
Synchronization of movement is defined as similar movements between two or more people who are temporally aligned. This is different to mimicry. Muscular bonding is the idea; this sparked some of the first research into movement synchronization and its effects on human emotion. In groups, synchronization of movement has been shown to increase conformity and trust however more research on group synchronization is needed to determine its effects on the group as a whole and on individuals within a group. In dyads, groups of two people, synchronization has been demonstrated to increase affiliation, self-esteem and altruistic behaviour and increase rapport. During arguments, synchrony between the arguing pair has been noted to decrease, however it is not clear whether this is due to the change in emotion or other factors. There is evidence to show that movement synchronization requires other people to cause its beneficial effects, as the effect on affiliation does not occur when one of the dyad is synchronizing their movements to something outside the dyad.
This is known as interpersonal synchrony. There has been dispute regarding the true effect of synchrony in these studies. Research in this area detailing the positive effects of synchrony, have attributed this to synchrony alone. Indeed, the Reinforcement of Cooperation Model suggests that perception of synchrony leads to reinforcement that cooperation is occurring, which leads to the pro-social effects of synchrony. More research is required to separate the effect of intentionality from the beneficial effect of synchrony. Film synchronization of image and sound in sound film. Synchronization is important in fields such as digital telephony and digital audio where streams of sam
The µ-law algorithm is a companding algorithm used in 8-bit PCM digital telecommunication systems in North America and Japan. It is one of two versions of the G.711 standard from ITU-T, the other version being the similar A-law, used in regions where digital telecommunication signals are carried on E-1 circuits, e.g. Europe. Companding algorithms reduce the dynamic range of an audio signal. In analog systems, this can increase the signal-to-noise ratio achieved during transmission; these SNR increases can be traded instead for reduced bandwidth for equivalent SNR. The µ-law algorithm may be described in a quantized digital form. For a given input x, the equation for μ-law encoding is F = sgn ln ln − 1 ≤ x ≤ 1 where μ = 255 in the North American and Japanese standards and sgn is the sign function, it is important to note that the range of this function is −1 to 1. Μ-law expansion is given by the inverse equation: F − 1 = sgn − 1 ≤ y ≤ 1 The discrete form is defined in ITU-T Recommendation G.711.
G. 711 is unclear about. However, G.191 provides example code in the C language for a μ-law encoder. The difference between the positive and negative ranges, e.g. the negative range corresponding to +30 to +1 is −31 to −2. This is accounted for by the use of 1's complement rather than 2's complement to convert a negative value to a positive value during encoding; the µ-law algorithm may be implemented in several ways: Analog Use an amplifier with non-linear gain to achieve companding in the analog domain. Non-linear ADC Use an analog-to-digital converter with quantization levels which are unequally spaced to match the μ-law algorithm. Digital Use the quantized digital version of the μ-law algorithm to convert data once it is in the digital domain. Μ-law encoding is used. In analog signal transmission, in the presence of constant background noise, the finer detail is lost. Given that the precision of the detail is compromised anyway, assuming that the signal is to be perceived as audio by a human, one can take advantage of the fact that the perceived acoustic intensity level or loudness is logarithmic by compressing the signal using a logarithmic-response operational amplifier.
In telecommunications circuits, most of the noise is injected on the lines, thus after the compressor, the intended signal is perceived as louder than the static, compared to an un-compressed source. This became a common solution, thus, prior to common digital usage, the μ-law specification was developed to define an interoperable standard. In digital systems this pre-existing algorithm had the effect of reducing the number of bits needed to encode recognizable human voice. Using μ-law, a sample could be encoded in as few as 8 bits, a sample size that conveniently matched the symbol size of most standard computers. Μ-law encoding reduced the dynamic range of the signal, thereby increasing the coding efficiency while biasing the signal in a way that results in a signal-to-distortion ratio, greater than that obtained by linear encoding for a given number of bits. The μ-law algorithm is used in the.au format, which dates back at least to the SPARCstation 1 by Sun Microsystems as the native method used by the /dev/audio interface used as a de facto standard for sound on Unix systems.
The au format is used in various common audio APIs such as the classes in the sun.audio Java package in Java 1.1 and in some C# methods. This plot illustrates; the abscissa represents the byte values 0-255 and the vertical axis is the 16-bit linear decoded value of μ-law encoding. The µ-law algorithm provides a larger dynamic range than the A-law at the cost of worse proportional distortions for small signals. By convention, A-law is used for an international connection. Audio level compression Signal compression G.711 This article incorporates public domain material from the General Services Administration document "Federal Standard 1037C". Waveform Coding Techniques – details of implementation A-Law and mu-Law Companding Implementations Using the TMS320C54x TMS320C6000 μ-Law and A-Law Companding with Software or the McBSP A-law and μ-law realisation
Integrated Services Digital Network
Integrated Services Digital Network is a set of communication standards for simultaneous digital transmission of voice, video and other network services over the traditional circuits of the public switched telephone network. It was first defined in 1988 in the CCITT red book. Prior to ISDN, the telephone system was viewed as a way to transport voice, with some special services available for data; the key feature of ISDN is that it integrates speech and data on the same lines, adding features that were not available in the classic telephone system. The ISDN standards define several kinds of access interfaces, such as Basic Rate Interface, Primary Rate Interface, Narrowband ISDN, Broadband ISDN. ISDN is a circuit-switched telephone network system, which provides access to packet switched networks, designed to allow digital transmission of voice and data over ordinary telephone copper wires, resulting in better voice quality than an analog phone can provide, it offers circuit-switched connections, packet-switched connections, in increments of 64 kilobit/s.
In some countries, ISDN found major market application for Internet access, in which ISDN provides a maximum of 128 kbit/s bandwidth in both upstream and downstream directions. Channel bonding can achieve a greater data rate. ISDN is employed as data-link and physical layers in the context of the OSI model. In common use, ISDN is limited to usage to Q.931 and related protocols, which are a set of signaling protocols establishing and breaking circuit-switched connections, for advanced calling features for the user. They were introduced in 1986. In a videoconference, ISDN provides simultaneous voice and text transmission between individual desktop videoconferencing systems and group videoconferencing systems. Integrated services refers to ISDN's ability to deliver at minimum two simultaneous connections, in any combination of data, voice and fax, over a single line. Multiple devices can be attached to the line, used as needed; that means an ISDN line can take care of what were expected to be most people's complete communications needs at a much higher transmission rate, without forcing the purchase of multiple analog phone lines.
It refers to integrated switching and transmission in that telephone switching and carrier wave transmission are integrated rather than separate as in earlier technology. The entry level interface to ISDN is the Basic Rate Interface, a 128 kbit/s service delivered over a pair of standard telephone copper wires; the 144 kbit/s overall payload rate is divided into two 64 kbit/s bearer channels and one 16 kbit/s signaling channel. This is sometimes referred to as 2B+D; the interface specifies the following network interfaces: The U interface is a two-wire interface between the exchange and a network terminating unit, the demarcation point in non-North American networks. The T interface is a serial interface between a computing device and a terminal adapter, the digital equivalent of a modem; the S interface is a four-wire bus. The R interface defines the point between a non-ISDN device and a terminal adapter which provides translation to and from such a device. BRI-ISDN is popular in Europe but is much less common in North America.
It is common in Japan — where it is known as INS64. The other ISDN access available is the Primary Rate Interface, carried over T-carrier with 24 time slots in North America, over E-carrier with 32 channels in most other countries; each channel provides transmission at a 64 kbit/s data rate. With the E1 carrier, the available channels are divided into 30 bearer channels, one data channel, one timing and alarm channel; this scheme is referred to as 30B+2D. In North America, PRI service is delivered via T1 carriers with only one data channel referred to as 23B+D, a total data rate of 1544 kbit/s. Non-Facility Associated Signalling allows two or more PRI circuits to be controlled by a single D channel, sometimes called 23B+D + n*24B. D-channel backup allows for a second D channel in case the primary fails. NFAS is used on a Digital Signal 3. PRI-ISDN is popular throughout the world for connecting private branch exchanges to the public switched telephone network. Though many network professionals use the term ISDN to refer to the lower-bandwidth BRI circuit, in North America BRI is uncommon whilst PRI circuits serving PBXs are commonplace.
The bearer channel is a standard 64 kbit/s voice channel of 8 bits sampled at 8 kHz with G.711 encoding. B-channels can be used to carry data, since they are nothing more than digital channels; each one of these channels is known as a DS0. Most B channels can carry a 64 kbit/s signal, but some were limited to 56K because they traveled over RBS lines; this has since become less so. X.25 can be carried over the B or D channels of a BRI line, over the B channels of a PRI line. X.25 over the D channel is used at many point-of-sale terminals because it eliminates the modem setup, because it connects to the central system over a B channel, thereby eliminating the need for modems and making much better use of the central system's telephone lines. X.25 was part of an ISDN protocol