text:
Minimum spanning tree

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.

Possible multiplicity
If there are $n$ vertices in the graph, then each spanning tree has $n − 1$ edges.

There may be several minimum spanning trees of the same weight; in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum.

Uniqueness
If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

Proof:
 * 1) Assume the contrary, that there are two different MSTs $A$ and $B$.
 * 2) Since $A$ and $B$ differ despite containing the same nodes, there is at least one edge that belongs to one but not the other.  Among such edges, let $e1$ be the one with least weight; this choice is unique because the edge weights are all distinct.  Without loss of generality, assume $e1$ is in $A$.
 * 3) As $B$ is an MST, ${e1} ∪ B$ must contain a cycle $C$ with $e1$.
 * 4) As a tree, $A$ contains no cycles, therefore $C$ must have an edge $e2$ that is not in $A$.
 * 5) Since $e1$ was chosen as the unique lowest-weight edge among those belonging to exactly one of $A$ and $B$, the weight of $e2$ must be greater than the weight of $e1$.
 * 6) As $e1$ and $e2$ are part of the cycle $C$, replacing $e2$ with $e1$ in $B$ therefore yields a spanning tree with a smaller weight.
 * 7) This contradicts the assumption that $B$ is an MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.

Minimum-cost subgraph
If the weights are positive, then a minimum spanning tree is, in fact, a minimum-cost subgraph connecting all vertices, since if a subgraph contains a cycle, removing any edge along that cycle will decrease its cost and preserve connectivity.

Cycle property
For any cycle $C$ in the graph, if the weight of an edge $e$ of $C$ is larger than any of the individual weights of all other edges of $C$, then this edge cannot belong to an MST.

Proof: Assume the contrary, i.e. that $e$ belongs to an MST $T1$. Then deleting $e$ will break $T1$ into two subtrees with the two ends of $e$ in different subtrees. The remainder of $C$ reconnects the subtrees, hence there is an edge $f$ of $C$ with ends in different subtrees, i.e., it reconnects the subtrees into a tree $T2$ with weight less than that of $T1$, because the weight of $f$ is less than the weight of $e$.

Cut property

For any cut $T$ of the graph, if the weight of an edge $BC$ in the cut-set of $EC$ is strictly smaller than the weights of all other edges of the cut-set of $EF$, then this edge belongs to all MSTs of the graph.

Proof: Assume that there is an MST $T$ that does not contain $C$. Adding $e$ to $C$ will produce a cycle, that crosses the cut once at $C$ and crosses back at another edge $T$. Deleting $e$ we get a spanning tree $S = {A,B,D,E},$ of strictly smaller weight than $e$. This contradicts the assumption that $T$ was a MST.

By a similar argument, if more than one edge is of minimum weight across a cut, then each such edge is contained in some minimum spanning tree.

Minimum-cost edge
If the minimum cost edge $e$ of a graph is unique, then this edge is included in any MST.

Proof: if $e'$ was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding $e'$ to the MST, would yield a spanning tree of smaller weight.

Contraction
If $T$ is a tree of MST edges, then we can contract $T$ into a single vertex while maintaining the invariant that the MST of the contracted graph plus $e$ gives the MST for the graph before contraction.

Algorithms
In all of the algorithms below, $e$ is the number of edges in the graph and $e$ is the number of vertices.

Classic algorithms
The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Borůvka's algorithm). Its purpose was an efficient electrical coverage of Moravia. The algorithm proceeds in a sequence of stages. In each stage, called Boruvka step, it identifies a forest $T$ consisting of the minimum-weight edge incident to each vertex in the graph $T$, then forms the graph $V – S = {C,F},$ as the input to the next step. Here $(S, V – S)$ denotes the graph derived from $T$ by contracting edges in $m$ (by the Cut property, these edges belong to the MST). Each Boruvka step takes linear time. Since the number of vertices is reduced by at least half in each step, Boruvka's algorithm takes $S ∪ {e}$ time.

A second algorithm is Prim's algorithm, which was invented by Vojtěch Jarník in 1930 and rediscovered by Prim in 1957 and Dijkstra in 1959. Basically, it grows the MST ($n$) one edge at a time. Initially, $F$ contains an arbitrary vertex. In each step, $G$ is augmented with a least-weight edge $T∖{e' } ∪ {e}$ such that $G$ is in $F$ and $T$ is not yet in $T$. By the Cut property, all edges added to $T$ are in the MST. Its run-time is either $G1 = G \ F$ or $G \ F$, depending on the data-structures used.

A third algorithm commonly in use is Kruskal's algorithm, which also takes $O(m log n)$ time.

A fourth algorithm, not as commonly used, is the reverse-delete algorithm, which is the reverse of Kruskal's algorithm. Its runtime is $(x,y)$.

All four of these are greedy algorithms. Since they run in polynomial time, the problem of finding such trees is in FP, and related decision problems such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in P.

Faster algorithms
Several researchers have tried to find more computationally-efficient algorithms.

In a comparison model, in which the only allowed operations on edge weights are pairwise comparisons, found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm.

The fastest non-randomized comparison-based algorithm with known complexity, by Bernard Chazelle, is based on the soft heap, an approximate priority queue. Its running time is $O(m log n)$, where $O(m + n log n)$ is the classical functional inverse of the Ackermann function. The function $O(m log n)$ grows extremely slowly, so that for all practical purposes it may be considered a constant no greater than 4; thus Chazelle's algorithm takes very close to linear time.

Dense graphs
If the graph is dense (i.e. $O(m log n (log log n)3)$, then a deterministic algorithm by Fredman and Tarjan finds the MST in time $O(m α(m,n))$. The algorithm executes a number of phases. Each phase executes Prim's algorithm many times, each for a limited number of steps. The run-time of each phase is $α$. If the number of vertices before a phase is $x$, the number of vertices remaining after a phase is at most $$\tfrac{n'}{2^{m/n'}}$$. Hence, at most $α$ phases are needed, which gives a linear run-time for dense graphs.

There are other algorithms that work in linear time on dense graphs.

Integer weights
If the edge weights are integers represented in binary, then deterministic algorithms are known that solve the problem in $m/n ≥ log log log n)$ integer operations. Whether the problem can be solved deterministically for a general graph in linear time by a comparison-based algorithm remains an open question.

Decision trees
Given graph $T$ where the nodes and edges are fixed but the weights are unknown, it is possible to construct a binary decision tree (DT) for calculating the MST for any permutation of weights. Each internal node of the DT contains a comparison between two edges, e.g. "Is the weight of the edge between $y$ and $T$ larger than the weight of the edge between $T$ and $n'$?". The two children of the node correspond to the two possible answers "yes" or "no". In each leaf of the DT, there is a list of edges from $G$ that correspond to an MST. The runtime complexity of a DT is the largest number of queries required to find the MST, which is just the depth of the DT. A DT for a graph $x$ is called optimal if it has the smallest depth of all correct DTs for $y$.

For every integer $w$, it is possible to find optimal decision trees for all graphs on $z$ vertices by brute-force search. This search proceeds in two steps.

A. Generating all potential DTs
 * There are $$2^{r \choose 2}$$ different graphs on $G$ vertices.
 * For each graph, an MST can always be found using $O(m)$ comparisons, e.g. by Prim's algorithm.
 * Hence, the depth of an optimal DT is less than $O(m + n)$.
 * Hence, the number of internal nodes in an optimal DT is less than $$2^{r^2}$$.
 * Every internal node compares two edges. The number of edges is at most $log*n$ so the different number of comparisons is at most $O(m + n)$.
 * Hence, the number of potential DTs is less than

$${(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}.$$

B. Identifying the correct DTs To check if a DT is correct, it should be checked on all possible permutations of the edge weights.
 * The number of such permutations is at most $r(r – 1)$.
 * For each permutation, solve the MST problem on the given graph using any existing algorithm, and compare the result to the answer given by the DT.
 * The running time of any MST algorithm is at most $r2$, so the total time required to check all permutations is at most $r2$.

Hence, the total time required for finding an optimal DT for all graphs with $G$ vertices is:
 * $$2^{r \choose 2} \cdot r^{2^{(r^2+2)}} \cdot (r^2+1)!,$$

which is less than
 * $$2^{2^{r^2+o(r)}}.$$

Optimal algorithm
Seth Pettie and Vijaya Ramachandran have found a provably optimal deterministic comparison-based minimum spanning tree algorithm. The following is a simplified description of the algorithm.

 * 1) Let $r4$, where $G$ is the number of vertices. Find all optimal decision trees on $r$ vertices. This can be done in time $(r2)!$ (see Decision trees above).
 * 2) Partition the graph to components with at most $r$ vertices in each component. This partition uses a soft heap, which "corrupts" a small number of the edges of the graph.
 * 3) Use the optimal decision trees to find an MST for the uncorrupted subgraph within each component.
 * 4) Contract each connected component spanned by the MSTs to a single vertex, and apply any algorithm which works on dense graphs in time $r2$ to the contraction of the uncorrupted subgraph
 * 5) Add back the corrupted edges to the resulting forest to form a subgraph guaranteed to contain the minimum spanning tree, and smaller by a constant factor than the starting graph. Apply the optimal algorithm recursively to this graph.

The runtime of all steps in the algorithm is $(r2 + 1)!$, except for the step of using the decision trees. The runtime of this step is unknown, but it has been proved that it is optimal - no algorithm can do better than the optimal decision tree. Thus, this algorithm has the peculiar property that it is provably optimal although its runtime complexity is unknown.

Parallel and distributed algorithms
Research has also considered parallel algorithms for the minimum spanning tree problem. With a linear number of processors it is possible to solve the problem in $r = log log log n$ time.

The problem can also be approached in a distributed manner. If each node is considered a computer and no node knows anything except its own connected links, one can still calculate the distributed minimum spanning tree.

MST on complete graphs with random weights
Alan M. Frieze showed that given a complete graph on n vertices, with edge weights that are independent identically distributed random variables with distribution function $$F$$ satisfying $$F'(0) > 0$$, then as n approaches +∞ the expected weight of the MST approaches $$\zeta(3)/F'(0)$$, where $$\zeta$$ is the Riemann zeta function (more specifically is $$\zeta(3)$$ Apéry's constant). Frieze and Steele also proved convergence in probability. Svante Janson proved a central limit theorem for weight of the MST.

For uniform random weights in $$[0,1]$$, the exact expected size of the minimum spanning tree has been computed for small complete graphs.

Fractional variant
There is a fractional variant of the MST, in which each edge is allowed to appear "fractionally". Formally, a fractional spanning set of a graph (V,E) is a nonnegative function f on E such that, for every non-trivial subset W of V (i.e., W is neither empty nor equal to V), the sum of f(e) over all edges connecting a node of W with a node of V\W is at least 1. Intuitively, f(e) represents the fraction of e that is contained in the spanning set. A minimum fractional spanning set is a fractional spanning set for which the sum $$\sum_{e\in E} f(e)\cdot w(e)$$ is as small as possible.

If the fractions f(e) are forced to be in {0,1}, then the set T of edges with f(e)=1 are a spanning set, as every node or subset of nodes is connected to the rest of the graph by at least one edge of T. Moreover, if f minimizes$$\sum_{e\in E} f(e)\cdot w(e)$$, then the resulting spanning set is necessarily a tree, since if it contained a cycle, then an edge could be removed without affecting the spanning condition. So the minimum fractional spanning set problem is a relaxation of the MST problem, and can also be called the fractional MST problem.

The fractional MST problem can be solved in polynomial time using the ellipsoid method. However, if we add a requirement that f(e) must be half-integer (that is, f(e) must be in {0, 1/2, 1}), then the problem becomes NP-hard, since it includes as a special case the Hamiltonian cycle problem: in an $$n$$-vertex unweighted graph, a half-integer MST of weight $$n/2$$ can only be obtained by assigning weight 1/2 to each edge of a Hamiltonian cycle.

Other variants

 * The Steiner tree of a subset of the vertices is the minimum tree that spans the given subset. Finding the Steiner tree is NP-Complete.

 * The k-minimum spanning tree (k-MST) is the tree that spans some subset of k vertices in the graph with minimum weight.
 * A set of k-smallest spanning trees is a subset of k spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight.   (Note that this problem is unrelated to the k-minimum spanning tree.)
 * The Euclidean minimum spanning tree is a spanning tree of a graph with edge weights corresponding to the Euclidean distance between vertices which are points in the plane (or space).
 * The rectilinear minimum spanning tree is a spanning tree of a graph with edge weights corresponding to the rectilinear distance between vertices which are points in the plane (or space).
 * The distributed minimum spanning tree is an extension of MST to the distributed model, where each node is considered a computer and no node knows anything except its own connected links. The mathematical definition of the problem is the same but there are different approaches for a solution.
 * The capacitated minimum spanning tree is a tree that has a marked node (origin, or root) and each of the subtrees attached to the node contains no more than c nodes. c is called a tree capacity. Solving CMST optimally is NP-hard, but good heuristics such as Esau-Williams and Sharma produce solutions close to optimal in polynomial time.
 * The degree-constrained minimum spanning tree is a MST in which each vertex is connected to no more than d other vertices, for some given number d. The case d = 2 is a special case of the traveling salesman problem, so the degree constrained minimum spanning tree is NP-hard in general.
 * An arborescence is a variant of MST for directed graphs. It can be solved in $$O(E + V \log V)$$ time using the Chu–Liu/Edmonds algorithm.
 * A maximum spanning tree is a spanning tree with weight greater than or equal to the weight of every other spanning tree. Such a tree can be found with algorithms such as Prim's or Kruskal's after multiplying the edge weights by -1 and solving the MST problem on the new graph. A path in the maximum spanning tree is the widest path in the graph between its two endpoints: among all possible paths, it maximizes the weight of the minimum-weight edge. Maximum spanning trees find applications in parsing algorithms for natural languages and in training algorithms for conditional random fields.
 * The dynamic MST problem concerns the update of a previously computed MST after an edge weight change in the original graph or the insertion/deletion of a vertex.
 * The minimum labeling spanning tree problem is to find a spanning tree with least types of labels if each edge in a graph is associated with a label from a finite label set instead of a weight.
 * A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree (or MBST) if the graph does not contain a spanning tree with a smaller bottleneck edge weight. A MST is necessarily a MBST (provable by the cut property), but a MBST is not necessarily a MST.
 * A minimum-cost spanning tree game is a cooperative game in which the players have to share among them the costs of constructing the optimal spanning tree.
 * The optimal network design problem is the problem of computing a set, subject to a budget constraint, which contains a spanning tree, such that the sum of shortest paths between every pair of nodes is as small as possible.

Applications
Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids (which they were first invented for, as mentioned above). They are invoked as subroutines in algorithms for other problems, including the Christofides algorithm for approximating the traveling salesman problem, approximating the multi-terminal minimum cut problem (which is equivalent in the single-terminal case to the maximum flow problem), and approximating the minimum-cost weighted perfect matching.

Other practical applications based on minimal spanning trees include:
 * Taxonomy.
 * Cluster analysis: clustering points in the plane, single-linkage clustering (a method of hierarchical clustering), graph-theoretic clustering, and clustering gene expression data.
 * Constructing trees for broadcasting in computer networks.
 * Image registration and segmentation – see minimum spanning tree-based segmentation.
 * Curvilinear feature extraction in computer vision.
 * Handwriting recognition of mathematical expressions.
 * Circuit design: implementing efficient multiple constant multiplications, as used in finite impulse response filters.
 * Regionalisation of socio-geographic areas, the grouping of areas into homogeneous, contiguous regions.
 * Comparing ecotoxicology data.
 * Topological observability in power systems.
 * Measuring homogeneity of two-dimensional materials.
 * Minimax process control.
 * Minimum spanning trees can also be used to describe financial markets. A correlation matrix can be created by calculating a coefficient of correlation between any two stocks. This matrix can be represented topologically as a complex network and a minimum spanning tree can be constructed to visualize relationships.

title: Minimum spanning tree


text:
Time-division multiplexing

Time-division multiplexing (TDM) is a method of transmitting and receiving independent signals over a common signal path by means of synchronized switches at each end of the transmission line so that each signal appears on the line only a fraction of time according to agreed rules, e.g. with each transmitter working in turn. It can be used when the bit rate of the transmission medium exceeds that of the signal to be transmitted. This form of signal multiplexing was developed in telecommunications for telegraphy systems in the late 19th century but found its most common application in digital telephony in the second half of the 20th century.

History
Time-division multiplexing was first developed for applications in telegraphy to route multiple transmissions simultaneously over a single transmission line. In the 1870s, Émile Baudot developed a time-multiplexing system of multiple Hughes telegraph machines.

In 1944, the British Army used the Wireless Set No. 10 to multiplex 10 telephone conversations over a microwave relay as far as 50 miles. This allowed commanders in the field to keep in contact with the staff in England across the English Channel.

In 1953, a 24-channel time-division multiplexer was placed in commercial operation by RCA Communications to send audio information between RCA's facility on Broad Street, New York, their transmitting station at Rocky Point and the receiving station at Riverhead, Long Island, New York. The communication was by a microwave system throughout Long Island. The experimental TDM system was developed by RCA Laboratories between 1950 and 1953.

In 1962, engineers from Bell Labs developed the first D1 channel banks, which combined 24 digitized voice calls over a four-wire copper trunk line between Bell central office analogue switches. A channel bank at each end of the line allowed the single line to carry short portions, each $1/undefined$ of a second, of up to 24 voice calls, in turn. The discrete signals on the trunk line carried 1.544 Mbit/s divided into $8,000$ separate frames per second, each composed of 24 contiguous octets and one framing bit. Each octet in a frame carried a single telephone call in turn. Thus each of 24 voice calls was encoded into two constant-bit-rate streams of 64 kbit/s (one in each direction), and converted back to conventional analog signals by the complementary equipment on the receiving end of the trunk line.

Technology
Time-division multiplexing is used primarily for digital signals but may be applied in analog multiplexing, as above, in which two or more signals or bit streams are transferred appearing simultaneously as sub-channels in one communication channel, but are physically taking turns on the channel. The time domain is divided into several recurrent time slots of fixed length, one for each sub-channel. A sample byte or data block of sub-channel 1 is transmitted during time slot 1, sub-channel 2 during time slot 2, etc. One TDM frame consists of one time slot per sub-channel, and usually a synchronization channel and sometimes an error correction channel. After all of these the cycle starts again with a new frame, starting with the second sample, byte or data block from sub-channel 1, etc.

Application examples

 * The plesiochronous digital hierarchy (PDH) system, also known as the PCM system, for digital transmission of several telephone calls over the same four-wire copper cable (T-carrier or E-carrier) or fiber in the circuit-switched digital telephone network
 * The synchronous digital hierarchy (SDH)/synchronous optical networking (SONET) network transmission standards that have replaced PDH
 * The Basic Rate Interface and Primary Rate Interface for the Integrated Services Digital Network (ISDN)
 * The RIFF (WAV) audio standard interleaves left and right stereo signals on a per-sample basis

TDM can be further extended into the time-division multiple access (TDMA) scheme, where several stations connected to the same physical medium, for example sharing the same frequency channel, can communicate. Application examples include:
 * The GSM telephone system
 * The Tactical Data Links Link 16 and Link 22

Multiplexed digital transmission
In circuit-switched networks, such as the public switched telephone network (PSTN), it is desirable to transmit multiple subscriber calls over the same transmission medium to effectively utilize the bandwidth of the medium. TDM allows transmitting and receiving telephone switches to create channels (tributaries) within a transmission stream. A standard DS0 voice signal has a data bit rate of 64 kbit/s. A TDM circuit runs at a much higher signal bandwidth, permitting the bandwidth to be divided into time frames (time slots) for each voice signal which is multiplexed onto the line by the transmitter. If the TDM frame consists of n voice frames, the line bandwidth is n*64 kbit/s.

Each voice time slot in the TDM frame is called a channel. In European systems, standard TDM frames contain 30 digital voice channels (E1), and in American systems (T1), they contain 24 channels. Both standards also contain extra bits (or bit time slots) for signaling and synchronization bits.

Multiplexing more than 24 or 30 digital voice channels is called higher order multiplexing. Higher order multiplexing is accomplished by multiplexing the standard TDM frames. For example, a European 120 channel TDM frame is formed by multiplexing four standard 30 channel TDM frames. At each higher order multiplex, four TDM frames from the immediate lower order are combined, creating multiplexes with a bandwidth of n*64 kbit/s, where n = 120, 480, 1920, etc.

Telecommunications systems
There are three types of synchronous TDM: T1, SONET/SDH, and ISDN.

Plesiochronous digital hierarchy (PDH) was developed as a standard for multiplexing higher order frames. PDH created larger numbers of channels by multiplexing the standard Europeans 30 channel TDM frames. This solution worked for a while; however PDH suffered from several inherent drawbacks which ultimately resulted in the development of the Synchronous Digital Hierarchy (SDH). The requirements which drove the development of SDH were these:

 * Be synchronous – All clocks in the system must align with a reference clock.
 * Be service-oriented – SDH must route traffic from End Exchange to End Exchange without worrying about exchanges in between, where the bandwidth can be reserved at a fixed level for a fixed period of time.
 * Allow frames of any size to be removed or inserted into an SDH frame of any size.
 * Easily manageable with the capability of transferring management data across links.
 * Provide high levels of recovery from faults.
 * Provide high data rates by multiplexing any size frame, limited only by technology.
 * Give reduced bit rate errors.

SDH has become the primary transmission protocol in most PSTN networks. It was developed to allow streams 1.544 Mbit/s and above to be multiplexed, in order to create larger SDH frames known as Synchronous Transport Modules (STM). The STM-1 frame consists of smaller streams that are multiplexed to create a 155.52 Mbit/s frame. SDH can also multiplex packet based frames e.g. Ethernet, PPP and ATM.

While SDH is considered to be a transmission protocol (Layer 1 in the OSI Reference Model), it also performs some switching functions, as stated in the third bullet point requirement listed above. The most common SDH Networking functions are these:

 * SDH Crossconnect – The SDH Crossconnect is the SDH version of a time–space–time crosspoint switch. It connects any channel on any of its inputs to any channel on any of its outputs. The SDH Crossconnect is used in Transit Exchanges, where all inputs and outputs are connected to other exchanges.
 * SDH Add–Drop Multiplexer – The SDH Add–Drop Multiplexer (ADM) can add or remove any multiplexed frame down to 1.544 Mb. Below this level, standard TDM can be performed. SDH ADMs can also perform the task of an SDH Crossconnect and are used in End Exchanges where the channels from subscribers are connected to the core PSTN network.

SDH network functions are connected using high-speed optic fibre. Optic fibre uses light pulses to transmit data and is therefore extremely fast. Modern optic fibre transmission makes use of wavelength-division multiplexing (WDM) where signals transmitted across the fibre are transmitted at different wavelengths, creating additional channels for transmission. This increases the speed and capacity of the link, which in turn reduces both unit and total costs.

Statistical version
Statistical time-division multiplexing (STDM) is an advanced version of TDM in which both the address of the terminal and the data itself are transmitted together for better routing. Using STDM allows bandwidth to be split over one line. Many college and corporate campuses use this type of TDM to distribute bandwidth.

On a 10-Mbit line entering a network, STDM can be used to provide 178 terminals with a dedicated 56k connection (178 * 56k = 9.96 Mb). A more common use however is to only grant the bandwidth when that much is needed. STDM does not reserve a time slot for each terminal, rather it assigns a slot when the terminal is requiring data to be sent or received.

In its primary form, TDM is used for circuit mode communication with a fixed number of channels and constant bandwidth per channel. Bandwidth reservation distinguishes time-division multiplexing from statistical multiplexing such as statistical time-division multiplexing. In pure TDM, the time slots are recurrent in a fixed order and pre-allocated to the channels, rather than scheduled on a packet-by-packet basis.

In dynamic TDMA, a scheduling algorithm dynamically reserves a variable number of time slots in each frame to variable bit-rate data streams, based on the traffic demand of each data stream. Dynamic TDMA is used in:
 * HIPERLAN/2
 * Dynamic synchronous transfer mode
 * IEEE 802.16a

Asynchronous time-division multiplexing (ATDM), is an alternative nomenclature in which STDM designates synchronous time-division multiplexing, the older method that uses fixed time slots.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Time-division multiplexing


text:
Time-domain reflectometer

A time-domain reflectometer (TDR) is an electronic instrument used to determine the characteristics of electrical lines by observing reflected pulses. It can be used to characterize and locate faults in metallic cables (for example, twisted pair wire or coaxial cable), and to locate discontinuities in a connector, printed circuit board, or any other electrical path.

Description
A TDR measures reflections along a conductor. In order to measure those reflections, the TDR will transmit an incident signal onto the conductor and listen for its reflections. If the conductor is of a uniform impedance and is properly terminated, then there will be no reflections and the remaining incident signal will be absorbed at the far-end by the termination. Instead, if there are impedance variations, then some of the incident signal will be reflected back to the source. A TDR is similar in principle to radar.

The impedance of the discontinuity can be determined from the amplitude of the reflected signal. The distance to the reflecting impedance can also be determined from the time that a pulse takes to return. The limitation of this method is the minimum system rise time. The total rise time consists of the combined rise time of the driving pulse and that of the oscilloscope or sampler that monitors the reflections.

Method
The TDR analysis begins with the propagation of a step or impulse of energy into a system and the subsequent observation of the energy reflected by the system. By analyzing the magnitude, duration and shape of the reflected waveform, the nature of the impedance variation in the transmission system can be determined.

If a pure resistive load is placed on the output of the reflectometer and a step signal is applied, a step signal is observed on the display, and its height is a function of the resistance. The magnitude of the step produced by the resistive load may be expressed as a fraction of the input signal as given by:

$$\rho = \frac{R_L - Z_0}{R_L + Z_0}$$

where $$Z_0$$ is the characteristic impedance of the transmission line.

Reflection
Generally, the reflections will have the same shape as the incident signal, but their sign and magnitude depend on the change in impedance level. If there is a step increase in the impedance, then the reflection will have the same sign as the incident signal; if there is a step decrease in impedance, the reflection will have the opposite sign. The magnitude of the reflection depends not only on the amount of the impedance change, but also upon the loss in the conductor.

The reflections are measured at the output/input to the TDR and displayed or plotted as a function of time. Alternatively, the display can be read as a function of cable length because the speed of signal propagation is almost constant for a given transmission medium.

Because of its sensitivity to impedance variations, a TDR may be used to verify cable impedance characteristics, splice and connector locations and associated losses, and estimate cable lengths.

Incident signal
TDRs use different incident signals. Some TDRs transmit a pulse along the conductor; the resolution of such instruments is often the width of the pulse. Narrow pulses can offer good resolution, but they have high frequency signal components that are attenuated in long cables. The shape of the pulse is often a half cycle sinusoid. For longer cables, wider pulse widths are used.

Fast rise time steps are also used. Instead of looking for the reflection of a complete pulse, the instrument is concerned with the rising edge, which can be very fast. A 1970s technology TDR used steps with a rise time of 25 ps.

Still other TDRs transmit complex signals and detect reflections with correlation techniques. See spread-spectrum time-domain reflectometry.

Variations and extensions
The equivalent device for optical fiber is an optical time-domain reflectometer.

Time-domain transmissometry (TDT) is an analogous technique that measures the transmitted (rather than reflected) impulse. Together, they provide a powerful means of analysing electrical or optical transmission media such as coaxial cable and optical fiber.

Variations of TDR exist. For example, spread-spectrum time-domain reflectometry (SSTDR) is used to detect intermittent faults in complex and high-noise systems such as aircraft wiring. Coherent optical time domain reflectometry (COTDR) is another variant, used in optical systems, in which the returned signal is mixed with a local oscillator and then filtered to reduce noise.

Example traces
These traces were produced by a time-domain reflectometer made from common lab equipment connected to approximately 100 feet of coaxial cable having a characteristic impedance of 50 ohms. The propagation velocity of this cable is approximately 66% of the speed of light in a vacuum.

Explanation
If the far end of the cable is shorted, that is, terminated with an impedance of zero ohms, and when the rising edge of the pulse is launched down the cable, the voltage at the launching point "steps up" to a given value instantly and the pulse begins propagating in the cable towards the short. When the pulse encounters the short, no energy is absorbed at the far end. Instead, an inverted pulse reflects back from the short towards the launching end. It is only when this reflection finally reaches the launch point that the voltage at this point abruptly drops back to zero, signaling the presence of a short at the end of the cable. That is, the TDR has no indication that there is a short at the end of the cable until its emitted pulse can travel in the cable and the echo can return. It is only after this round-trip delay that the short can be detected by the TDR. With knowledge of the signal propagation speed in the particular cable-under-test, the distance to the short can be measured.

A similar effect occurs if the far end of the cable is an open circuit (terminated into an infinite impedance). In this case, though, the reflection from the far end is polarized identically with the original pulse and adds to it rather than cancelling it out. So after a round-trip delay, the voltage at the TDR abruptly jumps to twice the originally-applied voltage.

Perfect termination at the far end of the cable would entirely absorb the applied pulse without causing any reflection, rendering the determination of the actual length of the cable impossible. In practice, some small reflection is nearly always observed.

The magnitude of the reflection is referred to as the reflection coefficient or ρ. The coefficient ranges from 1 (open circuit) to −1 (short circuit). The value of zero means that there is no reflection. The reflection coefficient is calculated as follows:

$$\rho = \frac{Z_t - Z_o}{Z_t + Z_o}$$

Where Zo is defined as the characteristic impedance of the transmission medium and Zt is the impedance of the termination at the far end of the transmission line.

Any discontinuity can be viewed as a termination impedance and substituted as Zt. This includes abrupt changes in the characteristic impedance. As an example, a trace width on a printed circuit board doubled at its midsection would constitute a discontinuity. Some of the energy will be reflected back to the driving source; the remaining energy will be transmitted. This is also known as a scattering junction.

Usage
Time domain reflectometers are commonly used for in-place testing of very long cable runs, where it is impractical to dig up or remove what may be a kilometers-long cable. They are indispensable for preventive maintenance of telecommunication lines, as TDRs can detect resistance on joints and connectors as they corrode, and increasing insulation leakage as it degrades and absorbs moisture, long before either leads to catastrophic failures. Using a TDR, it is possible to pinpoint a fault to within centimetres.

TDRs are also very useful tools for technical surveillance counter-measures, where they help determine the existence and location of wire taps. The slight change in line impedance caused by the introduction of a tap or splice will show up on the screen of a TDR when connected to a phone line.

TDR equipment is also an essential tool in the failure analysis of modern high-frequency printed circuit boards with signal traces crafted to emulate transmission lines. By observing reflections, any unsoldered pins of a ball grid array device can be detected. Short circuited pins can also be detected in a similar fashion.

The TDR principle is used in industrial settings, in situations as diverse as the testing of integrated circuit packages to measuring liquid levels. In the former, the time domain reflectometer is used to isolate failing sites in the same. The latter is primarily limited to the process industry.

In level measurement
In a TDR-based level measurement device, the device generates an impulse that propagates down a thin waveguide (referred to as a probe) – typically a metal rod or a steel cable. When this impulse hits the surface of the medium to be measured, part of the impulse reflects back up the waveguide. The device determines the fluid level by measuring the time difference between when the impulse was sent and when the reflection returned. The sensors can output the analyzed level as a continuous analog signal or switch output signals. In TDR technology, the impulse velocity is primarily affected by the permittivity of the medium through which the pulse propagates, which can vary greatly by the moisture content and temperature of the medium. In many cases, this effect can be corrected without undue difficulty. In some cases, such as in boiling and/or high temperature environments, the correction can be difficult. In particular, determining the froth (foam) height and the collapsed liquid level in a frothy / boiling medium can be very difficult.

Used in anchor cables in dams
The Dam Safety Interest Group of CEA Technologies, Inc. (CEATI), a consortium of electrical power organizations, has applied Spread-spectrum time-domain reflectometry to identify potential faults in concrete dam anchor cables. The key benefit of Time Domain reflectometry over other testing methods is the non-destructive method of these tests.

Used in the earth and agricultural sciences
A TDR is used to determine moisture content in soil and porous media. Over the last two decades, substantial advances have been made measuring moisture in soil, grain, food stuff, and sediment. The key to TDR's success is its ability to accurately determine the permittivity (dielectric constant) of a material from wave propagation, due to the strong relationship between the permittivity of a material and its water content, as demonstrated in the pioneering works of Hoekstra and Delaney (1974) and Topp et al. (1980). Recent reviews and reference work on the subject include, Topp and Reynolds (1998), Noborio (2001), Pettinellia et al. (2002), Topp and Ferre (2002) and Robinson et al. (2003). The TDR method is a transmission line technique, and determines apparent permittivity (Ka) from the travel time of an electromagnetic wave that propagates along a transmission line, usually two or more parallel metal rods embedded in soil or sediment. The probes are typically between 10 and 30 cm long and connected to the TDR via coaxial cable.

In geotechnical engineering
Time domain reflectometry has also been utilized to monitor slope movement in a variety of geotechnical settings including highway cuts, rail beds, and open pit mines (Dowding & O'Connor, 1984, 2000a, 2000b; Kane & Beck, 1999). In stability monitoring applications using TDR, a coaxial cable is installed in a vertical borehole passing through the region of concern. The electrical impedance at any point along a coaxial cable changes with deformation of the insulator between the conductors. A brittle grout surrounds the cable to translate earth movement into an abrupt cable deformation that shows up as a detectable peak in the reflectance trace. Until recently, the technique was relatively insensitive to small slope movements and could not be automated because it relied on human detection of changes in the reflectance trace over time. Farrington and Sargand (2004) developed a simple signal processing technique using numerical derivatives to extract reliable indications of slope movement from the TDR data much earlier than by conventional interpretation.

Another application of TDRs in geotechnical engineering is to determine the soil moisture content. This can be done by placing the TDRs in different soil layers and measurement of the time of start of precipitation and the time that TDR indicate an increase in the soil moisture content. The depth of the TDR (d) is a known factor and the other is the time it takes the drop of water to reach that depth (t); therefore the speed of water infiltration (v) can be determined. This is a good method to assess the effectiveness of Best Management Practices (BMPs) in reducing stormwater surface runoff.

In semiconductor device analysis
Time domain reflectometry is used in semiconductor failure analysis as a non-destructive method for the location of defects in semiconductor device packages. The TDR provides an electrical signature of individual conductive traces in the device package, and is useful for determining the location of opens and shorts.

In aviation wiring maintenance
Time domain reflectometry, specifically spread-spectrum time-domain reflectometry is used on aviation wiring for both preventive maintenance and fault location. Spread spectrum time domain reflectometry has the advantage of precisely locating the fault location within thousands of miles of aviation wiring. Additionally, this technology is worth considering for real time aviation monitoring, as spread spectrum reflectometry can be employed on live wires.

This method has been shown to be useful to locating intermittent electrical faults.

Multi carrier time domain reflectometry (MCTDR) has also been identified as a promising method for embedded EWIS diagnosis or troubleshooting tools. Based on the injection of a multicarrier signal (respecting EMC and harmless for the wires), this smart technology provides information for the detection, localization and characterization of electrical defects (or mechanical defects having electrical consequences) in the wiring systems. Hard fault (short, open circuit) or intermittent defects can be detected very quickly increasing the reliability of wiring systems and improving their maintenance.

title: Time-domain reflectometer


text:
Time standard

A time standard is a specification for measuring time: either the rate at which time passes or points in time or both. In modern times, several time specifications have been officially recognized as standards, where formerly they were matters of custom and practice. An example of a kind of time standard can be a time scale, specifying a method for measuring divisions of time. A standard for civil time can specify both time intervals and time-of-day.

Standardized time measurements are made using a clock to count periods of some period changes, which may be either the changes of a natural phenomenon or of an artificial machine.

Historically, time standards were often based on the Earth's rotational period. From the late 18 century to the 19th century it was assumed that the Earth's daily rotational rate was constant. Astronomical observations of several kinds, including eclipse records, studied in the 19th century, raised suspicions that the rate at which Earth rotates is gradually slowing and also shows small-scale irregularities, and this was confirmed in the early twentieth century. Time standards based on Earth rotation were replaced (or initially supplemented) for astronomical use from 1952 onwards by an ephemeris time standard based on the Earth's orbital period and in practice on the motion of the Moon. The invention in 1955 of the caesium atomic clock has led to the replacement of older and purely astronomical time standards, for most practical purposes, by newer time standards based wholly or partly on atomic time.

Various types of second and day are used as the basic time interval for most time scales. Other intervals of time (minutes, hours, and years) are usually defined in terms of these two.

Terminology
The term "time" is generally used for many close but different concepts, including:
 * instant as an object – one point on the time axis. Being an object, it has no value;
 * date as a quantity characterising an instant. As a quantity, it has a value which may be expressed in a variety of ways, for example "2014-04-26T09:42:36,75" in ISO standard format, or more colloquially such as "today, 9:42 a.m.";
 * time interval as an object – part of the time axis limited by two instants. Being an object, it has no value;
 * duration as a quantity characterizing a time interval. As a quantity, it has a value, such as a number of minutes, or may be described in terms of the quantities (such as times and dates) of its beginning and end.
 * chronology, an ordered sequence of events in the past. Chronologies can be put into chronological groups (periodization). One of the most important systems of periodization is the geologic time scale, which is a system of periodizing the events that shaped the Earth and its life. Chronology, periodization, and interpretation of the past are together known as the study of history.

Definitions of the second
There have only ever been three definitions of the second: as a fraction of the day, as a fraction of an extrapolated year, and as the microwave frequency of a caesium atomic clock.

In early history, clocks were not accurate enough to track seconds. After the invention of mechanical clocks, the CGS system and MKS system of units both defined the second as $1/undefined$ of a mean solar day. MKS was adopted internationally during the 1940s.

In the late 1940s, quartz crystal oscillator clocks could measure time more accurately than the rotation of the Earth. Metrologists also knew that Earth's orbit around the Sun (a year) was much more stable than Earth's rotation. This led to the definition of ephemeris time and the tropical year, and the ephemeris second was defined as "the fraction $1/undefined$ of the tropical year for 1900 January 0 at 12 hours ephemeris time". This definition was adopted as part of the International System of Units in 1960.

Most recently, atomic clocks have been developed that offer improved accuracy. Since 1967, the SI base unit for time is the SI second, defined as exactly "the duration of 9,192,631,770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the caesium-133 atom" (at a temperature of 0 K and at mean sea level). The SI second is the basis of all atomic timescales, e.g. coordinated universal time, GPS time, International Atomic Time, etc.

Current time standards
Geocentric Coordinate Time (TCG) is a coordinate time having its spatial origin at the center of Earth's mass. TCG is a theoretical ideal, and any particular realization will have measurement error.

International Atomic Time (TAI) is the primary physically realized time standard. TAI is produced by the International Bureau of Weights and Measures (BIPM), and is based on the combined input of many atomic clocks around the world, each corrected for environmental and relativistic effects (both gravitational and because of speed, like in GNSS). TAI is not related to TCG directly but rather is a realization of Terrestrial Time (TT), a theoretical timescale that is a rescaling of TCG such that the time rate approximately matches proper time at mean sea level.

Universal Time (UT1) is the Earth Rotation Angle (ERA) linearly scaled to match historical definitions of mean solar time at 0° longitude. At high precision, Earth's rotation is irregular and is determined from the positions of distant quasars using long baseline interferometry, laser ranging of the Moon and artificial satellites, as well as GPS satellite orbits.

Coordinated Universal Time (UTC) is an atomic time scale designed to approximate UT1. UTC differs from TAI by an integral number of seconds. UTC is kept within 0.9 second of UT1 by the introduction of one-second steps to UTC, the "leap second". To date these steps (and difference "TAI-UTC") have always been positive.

The Global Positioning System broadcasts a very precise time signal worldwide, along with instructions for converting GPS time (GPST) to UTC. It was defined with a constant offset from TAI: GPST = TAI - 19 s. The GPS time standard is maintained independently but regularly synchronized with or from, UTC time.

Standard time or civil time in a time zone deviates a fixed, round amount, usually a whole number of hours, from some form of Universal Time, usually UTC. The offset is chosen such that a new day starts approximately while the Sun is crossing the nadir meridian. Alternatively the difference is not really fixed, but it changes twice a year by a round amount, usually one hour, see Daylight saving time.

Julian day number is a count of days elapsed since Greenwich mean noon on 1 January 4713 B.C., Julian proleptic calendar. The Julian Date is the Julian day number followed by the fraction of the day elapsed since the preceding noon. Conveniently for astronomers, this avoids the date skip during an observation night. Modified Julian day (MJD) is defined as MJD = JD - 2400000.5. An MJD day thus begins at midnight, civil date. Julian dates can be expressed in UT1, TAI, TT, etc. and so for precise applications the timescale should be specified, e.g. MJD 49135.3824 TAI.

Barycentric Coordinate Time (TCB) is a coordinate time having its spatial origin at the center of mass of the Solar System, which is called the barycenter.

Conversions
Conversions between atomic time systems (TAI, GPST, and UTC) are for the most part exact. However, GPS time is a measured value as opposed to a computed "paper" scale. As such it may differ from UTC(USNO) by a few hundred nanoseconds, which in turn may differ from official UTC by as much as 26 nanoseconds. Conversions for UT1 and TT rely on published difference tables which are specified to 10 microseconds and 0.1 nanoseconds respectively. Definitions:
 * 1) LS = TAI − UTC = leap seconds from USNO Table of Leap Seconds
 * 2) DUT1 = UT1 − UTC published in IERS Bulletins or U.S. Naval Observatory EO
 * 3) DTT = TT − TAI − 32.184 s published in BIPM's TT(BIPM) tables.

TCG is linearly related to TT as: TCG − TT = LG × (JD − 2443144.5) × 86400 seconds, with the scale difference LG defined as 6.969290134 exactly.

TCB is a linear transformation of TDB and TDB differs from TT in small, mostly periodic terms. Neglecting these terms (on the order of 2 milliseconds for several millennia around the present epoch), TCB is related to TT by: TCB − TT = LB × (JD − 2443144.5) × 86400 seconds. The scale difference LB has been defined by the IAU to be 1.550519768e-08 exactly.

Time standards based on Earth rotation
Apparent solar time or true solar time is based on the solar day, which is the period between one solar noon (passage of the real Sun across the meridian) and the next. A solar day is approximately 24 hours of mean time. Because the Earth's orbit around the Sun is elliptical, and because of the obliquity of the Earth's axis relative to the plane of the orbit (the ecliptic), the apparent solar day varies a few dozen seconds above or below the mean value of 24 hours. As the variation accumulates over a few weeks, there are differences as large as 16 minutes between apparent solar time and mean solar time (see Equation of time). However, these variations cancel out over a year. There are also other perturbations such as Earth's wobble, but these are less than a second per year.

Sidereal time is time by the stars. A sidereal rotation is the time it takes the Earth to make one revolution with rotation to the stars, approximately 23 hours 56 minutes 4 seconds. A mean solar day is about 3 minutes 56 seconds longer than a mean sidereal day, or more than a mean sidereal day. In astronomy, sidereal time is used to predict when a star will reach its highest point in the sky. For accurate astronomical work on land, it was usual to observe sidereal time rather than solar time to measure mean solar time, because the observations of 'fixed' stars could be measured and reduced more accurately than observations of the Sun (in spite of the need to make various small compensations, for refraction, aberration, precession, nutation and proper motion). It is well known that observations of the Sun pose substantial obstacles to the achievement of accuracy in measurement. In former times, before the distribution of accurate time signals, it was part of the routine work at any observatory to observe the sidereal times of meridian transit of selected 'clock stars' (of well-known position and movement), and to use these to correct observatory clocks running local mean sidereal time; but nowadays local sidereal time is usually generated by computer, based on time signals.

Mean solar time was a time standard used especially at sea for navigational purposes, calculated by observing apparent solar time and then adding to it a correction, the equation of time, which compensated for two known irregularities in the length of the day, caused by the ellipticity of the Earth's orbit and the obliquity of the Earth's equator and polar axis to the ecliptic (which is the plane of the Earth's orbit around the sun). It has been superseded by Universal Time.

Greenwich Mean Time was originally mean time deduced from meridian observations made at the Royal Greenwich Observatory (RGO). The principal meridian of that observatory was chosen in 1884 by the International Meridian Conference to be the Prime Meridian. GMT either by that name or as 'mean time at Greenwich' used to be an international time standard, but is no longer so; it was initially renamed in 1928 as Universal Time (UT) (partly as a result of ambiguities arising from the changed practice of starting the astronomical day at midnight instead of at noon, adopted as from 1 January 1925). UT1 is still in reality mean time at Greenwich. Today, GMT is a time zone but is still the legal time in the UK in winter (and as adjusted by one hour for summer time). But Coordinated Universal Time (UTC) (an atomic-based time scale which is always kept within 0.9 second of UT1) is in common actual use in the UK, and the name GMT is often used to refer to it. (See articles Greenwich Mean Time, Universal Time, Coordinated Universal Time and the sources they cite.)

Versions of Universal Time such as UT0 and UT2 have been defined but are no longer in use.

Time standards for planetary motion calculations
Ephemeris time (ET) and its successor time scales described below have all been intended for astronomical use, e.g. in planetary motion calculations, with aims including uniformity, in particular, freedom from irregularities of Earth rotation. Some of these standards are examples of dynamical time scales and/or of coordinate time scales. Ephemeris Time was from 1952 to 1976 an official time scale standard of the International Astronomical Union; it was a dynamical time scale based on the orbital motion of the Earth around the Sun, from which the ephemeris second was derived as a defined fraction of the tropical year. This ephemeris second was the standard for the SI second from 1956 to 1967, and it was also the source for calibration of the caesium atomic clock; its length has been closely duplicated, to within 1 part in 1010, in the size of the current SI second referred to atomic time. This Ephemeris Time standard was non-relativistic and did not fulfil growing needs for relativistic coordinate time scales. It was in use for the official almanacs and planetary ephemerides from 1960 to 1983, and was replaced in official almanacs for 1984 and after, by numerically integrated Jet Propulsion Laboratory Development Ephemeris DE200 (based on the JPL relativistic coordinate time scale Teph).

For applications at the Earth's surface, ET's official replacement was Terrestrial Dynamical Time (TDT), which maintained continuity with it. TDT is a uniform atomic time scale, whose unit is the SI second. TDT is tied in its rate to the SI second, as is International Atomic Time (TAI), but because TAI was somewhat arbitrarily defined at its inception in 1958 to be initially equal to a refined version of UT, TDT was offset from TAI, by a constant 32.184 seconds. The offset provided a continuity from Ephemeris Time to TDT. TDT has since been redefined as Terrestrial Time (TT).

For the calculation of ephemerides, Barycentric Dynamical Time (TDB) was officially recommended to replace ET. TDB is similar to TDT but includes relativistic corrections that move the origin to the barycenter, hence it is a dynamical time at the barycenter. TDB differs from TT only in periodic terms. The difference is at most 2 milliseconds. Deficiencies were found in the definition of TDB (though not affecting Teph), and TDB has been replaced by Barycentric Coordinate Time (TCB) and Geocentric Coordinate Time (TCG), and redefined to be JPL ephemeris time argument Teph, a specific fixed linear transformation of TCB. As defined, TCB (as observed from the Earth's surface) is of divergent rate relative to all of ET, Teph and TDT/TT; and the same is true, to a lesser extent, of TCG. The ephemerides of Sun, Moon and planets in current widespread and official use continue to be those calculated at the Jet Propulsion Laboratory (updated as from 2003 to DE405) using as argument Teph.

title: Time standard


text:
T interface

A T-interface or T reference point is used for basic rate access in an Integrated Services Digital Network (ISDN) environment. It is a User–network interface reference point that is characterized by a four-wire, 144 kbit/s (2B+D) user rate.

Other characteristics of a T-interface are:
 * it accommodates the link access and transport layer function in the ISDN architecture
 * it is located at the user premises
 * it is distance sensitive to the servicing Network termination 1
 * it functions in a manner similar to that of the Channel service units (CSUs) and the Data service units (DSUs).

The T interface is electrically equivalent to the S interface, and the two are jointly referred to as the S/T interface.

title: T interface


text:
Toll switching trunk

In telecommunication, a toll switching trunk or toll connecting trunk is a trunk connecting an end office to a toll center as the first stage of concentration for intertoll or long-distance traffic.

Operator assistance or participation may be an optional function. In U.S. common carrier telephony service, a toll center designated Class 4C is an office where assistance in completing incoming calls is provided in addition to other traffic; a toll center designated Class 4P is an office where operators handle only outbound calls, or where switching is performed without operator assistance.

title: Toll switching trunk


text:
Total harmonic distortion

The total harmonic distortion (THD or THDi) is a measurement of the harmonic distortion present in a signal and is defined as the ratio of the sum of the powers of all harmonic components to the power of the fundamental frequency. Distortion factor, a closely related term, is sometimes used as a synonym.

In audio systems, lower distortion means the components in a loudspeaker, amplifier or microphone or other equipment produce a more accurate reproduction of an audio recording.

In radio communications, devices with lower THD tend to produce less unintentional interference with other electronic devices. Since harmonic distortion can potentially widen the frequency spectrum of the output emissions from a device by adding signals at multiples of the input frequency, devices with high THD are less suitable in applications such as spectrum sharing and spectrum sensing.

In power systems, lower THD implies lower peak currents, less heating, lower electromagnetic emissions, and less core loss in motors. IEEE std 519-2022 covers the recommended practice and requirements for harmonic control in electric power systems.

Definitions and examples
To understand a system with an input and an output, such as an audio amplifier, we start with an ideal system where the transfer function is linear and time-invariant. When a sinusoidal signal of frequency ω passes through a non-ideal, non-linear device, additional content is added at multiples nω (harmonics) of the original frequency. THD is a measure of that additional signal content not present in the input signal.

When the main performance criterion is the ″purity″ of the original sine wave (in other words, the contribution of the original frequency with respect to its harmonics), the measurement is most commonly defined as the ratio of the RMS amplitude of a set of higher harmonic frequencies to the RMS amplitude of the first harmonic, or fundamental, frequency

\mathrm{THD_F} \,= \,\frac{ \sqrt{V_2^2 + V_3^2 + V_4^2 + \cdots} }{V_1} $$ where Vn is the RMS value of the nth harmonic voltage and V1 is the RMS value of the fundamental component.

In practice, the THDF is commonly used in audio distortion specifications (percentage THD); however, THD is a non-standardized specification and the results between manufacturers are not easily comparable. Since individual harmonic amplitudes are measured, it is required that the manufacturer disclose the test signal frequency range, level and gain conditions, and number of measurements taken. It is possible to measure the full 20–20 kHz range using a sweep (though distortion for a fundamental above 10 kHz is inaudible).

Measurements for calculating the THD are made at the output of a device under specified conditions. The THD is usually expressed in percent or in dB relative to the fundamental as distortion attenuation.

A variant definition uses the fundamental plus harmonics as the reference:

\mathrm{THD_R} \,=\, \frac{ \sqrt{V_2^2 + V_3^2 + V_4^2 + \cdots} }{\sqrt{V_1^2 + V_2^2 + V_3^2 + \cdots}}\, = \,\frac{\mathrm{THD_F}}{\sqrt{1 + \mathrm{THD}^2_\mathrm{F}}} $$ These can be distinguished as THDF (for "fundamental"), and THDR (for "root mean square"). THDR cannot exceed 100%. At low distortion levels, the difference between the two calculation methods is negligible. For instance, a signal with THDF of 10% has a very similar THDR of 9.95%. However, at higher distortion levels the discrepancy becomes large. For instance, a signal with THDF 266% has a THDR of 94%. A pure square wave with infinite harmonics has THDF of 48.3%, or THDR of 43.5%.

Some use the term "distortion factor" as a synonym for THDR, while others use it as a synonym for THDF.

The International Electrotechnical Commission (IEC) also defines another term total harmonic factor for the "ratio of the RMS value of the harmonic content of an alternating quantity to the RMS value of the quantity" using a different equation.

THD+N
THD+N means total harmonic distortion plus noise. This measurement is much more common and more comparable between devices. It is usually measured by inputting a sine wave, notch filtering the output, and comparing the ratio between the output signal with and without the sine wave:

\mathrm{THD\!\!+\!\!N} = \frac{\displaystyle\sum_{n=2}^\infty{\text{harmonics}} + \text{noise}}{\text{fundamental}} $$

Like the THD measurement, this is a ratio of RMS amplitudes, and can be measured as THDF (bandpassed or calculated fundamental as the denominator) or, more commonly, as THDR (total distorted signal as the denominator).

A meaningful measurement must include the bandwidth of measurement. This measurement includes effects from ground loop power line hum, high-frequency interference, intermodulation distortion between these tones and the fundamental, and so on, in addition to harmonic distortion. For psychoacoustic measurements, a weighting curve is applied such as A-weighting or ITU-R BS.468, which is intended to accentuate what is most audible to the human ear, contributing to a more accurate measurement. A-weighting is a rough way to estimate the frequency sensitivity of every persons' ears, as it doesn't take into account the non-linear behavior of the ear. The loudness model proposed by Zwicker includes these complexities. The model is described in the German standard DIN45631

For a given input frequency and amplitude, THD+N is reciprocal to SINAD, provided that both measurements are made over the same bandwidth.

Measurement
The distortion of a waveform relative to a pure sinewave can be measured either by using a THD analyzer to analyse the output wave into its constituent harmonics and noting the amplitude of each relative to the fundamental; or by cancelling out the fundamental with a notch filter and measuring the remaining signal, which will be total aggregate harmonic distortion plus noise.

Given a sinewave generator of very low inherent distortion, it can be used as input to amplification equipment, whose distortion at different frequencies and signal levels can be measured by examining the output waveform.

There is electronic equipment both to generate sinewaves and to measure distortion; but a general-purpose digital computer equipped with a sound card can carry out harmonic analysis with suitable software. Different software can be used to generate sinewaves, but the inherent distortion may be too high for measurement of very low-distortion amplifiers.

Interpretation
For many purposes different types of harmonics are not equivalent. For instance, crossover distortion at a given THD is much more audible than clipping distortion at the same THD, since the harmonics produced by crossover distortion are nearly as strong at higher frequency harmonics, such as 10x to 20x the fundamental, as they are at lower-frequency harmonics like 3x or 5x the fundamental. Those harmonics appearing far away in frequency from a fundamental (desired signal) are not as easily masked by that fundamental. In contrast, at the onset of clipping, harmonics first appear at low order frequencies and gradually start to occupy higher frequency harmonics. A single THD number is therefore inadequate to specify audibility, and must be interpreted with care. Taking THD measurements at different output levels would expose whether the distortion is clipping (which decreases with an decreasing level) or crossover (which stays constant with varying output level, and thus is a greater percentage of the sound produced at low volumes).

THD is a summation of a number of harmonics equally weighted, even though research performed decades ago identifies that lower order harmonics are harder to hear at the same level, compared with higher order ones. In addition, even order harmonics are said to be generally harder to hear than odd order. A number of formulas that attempt to correlate THD with actual audibility have been published, but none have gained mainstream use.

Examples
For many standard signals, the above criterion may be calculated analytically in a closed form. For example, a pure square wave has THDF equal to

\mathrm{THD_F} \,= \,\sqrt{\frac{\,\pi^2}{8}-1\,}\approx \, 0.483\,=\,48.3\% $$ The sawtooth signal possesses

\mathrm{THD_F} \,= \,\sqrt{\frac{\,\pi^2}{6}-1\,}\approx \, 0.803\,=\,80.3\% $$ The pure symmetrical triangle wave has THDF of

\mathrm{THD_F} \,= \,\sqrt{\frac{\,\pi^4}{96}-1\,}\approx\,0.121\,= \, 12.1\% $$ For the rectangular pulse train with the duty cycle μ (called sometimes the cyclic ratio), the THDF has the form

\mathrm{THD_F}\,(\mu)=\sqrt{\frac{\mu(1-\mu)\pi^2\,}{2\sin^2\pi\mu}-1\;}\,,\qquad 0<\mu<1 $$ and logically, reaches the minimum (≈0.483) when the signal becomes symmetrical μ=0.5, i.e. the pure square wave. Appropriate filtering of these signals may drastically reduce the resulting THD. For instance, the pure square wave filtered by the Butterworth low-pass filter of the second-order (with the cutoff frequency set equal to the fundamental frequency) has THDF of 5.3%, while the same signal filtered by the fourth-order filter has THDF of 0.6%. However, analytic computation of the THDF for complicated waveforms and filters often represents a difficult task, and the resulting expressions may be quite laborious to obtain. For example, the closed-form expression for the THDF of the sawtooth wave filtered by the first-order Butterworth low-pass filter is simply

\mathrm{THD_F}\,= \, \sqrt{\frac{\,\pi^2}{3} - \pi\coth\pi\,}\,\approx\,0.370\,= \, 37.0\% $$ while that for the same signal filtered by the second-order Butterworth filter is given by a rather cumbersome formula

\mathrm{THD_F}\,= \sqrt{\pi\,\frac{\; \cot\dfrac{\pi}{\sqrt{2\,}}\cdot\coth^{2\!}\dfrac{\pi}{\sqrt{2\,}} -\cot^{2\!}\dfrac{\pi}{\sqrt{2\,}}\cdot\coth\dfrac{\pi}{\sqrt{2\,}} -\cot\dfrac{\pi}{\sqrt{2\,}} - \coth\dfrac{\pi}{\sqrt{2\,}}\;} {\sqrt{2\,}\left(\!\cot^{2\!}\dfrac{\pi}{\sqrt{2\,}} +\coth^{2\!}\dfrac{\pi}{\sqrt{2\,}}\!\right)} \,+\,\frac{\,\pi^2}{3} \,-\, 1\;} \;\approx\;0.181\,= \, 18.1\% $$ Yet, the closed-form expression for the THDF of the pulse train filtered by the pth-order Butterworth low-pass filter is even more complicated and has the following form

\mathrm{THD_F}\,(\mu, p)= \csc\pi\mu\,\cdot \!\sqrt{\mu(1-\mu)\pi^2-\,\sin^2\!\pi\mu\, -\,\frac{\,\pi}{2}\sum_{s=1}^{2p} \frac{\cot \pi z_s}{z_s^2} \prod\limits_{\scriptstyle l=1\atop\scriptstyle l\neq s}^{2p}\!\frac{1}{\,z_s-z_l\,}\, +\,\frac{\,\pi}{2}\,\mathrm{Re}\sum_{s=1}^{2p} \frac{e^{i\pi z_s(2\mu-1)}}{z_s^2\sin \pi z_s} \prod\limits_{\scriptstyle l=1\atop\scriptstyle l\neq s}^{2p}\!\frac{1}{\,z_s-z_l\,}\,} $$ where μ is the duty cycle, 0<μ<1, and

z_l\equiv \exp{\frac{i\pi(2l-1)}{2p}}\,, \qquad l=1, 2,\ldots, 2p $$ see for more details.

title: Total harmonic distortion


text:
Traffic intensity

In telecommunication networks, traffic intensity is a measure of the average occupancy of a server or resource during a specified period of time, normally a busy hour. It is measured in traffic units (erlangs) and defined as the ratio of the time during which a facility is cumulatively occupied to the time this facility is available for occupancy.

In a digital network, the traffic intensity is:
 * $$ \frac{a L}{R}$$

where
 * a is the average arrival rate of packets (e.g. in packets per second)
 * L is the average packet length (e.g. in bits), and
 * R is the transmission rate (e.g. bits per second)

A traffic intensity greater than one erlang means that the rate at which bits arrive exceeds the rate bits can be transmitted and queuing delay will grow without bound (if the traffic intensity stays the same). If the traffic intensity is less than one erlang, then the router can handle more average traffic.

Telecommunication operators are vitally interested in traffic intensity, as it dictates the amount of equipment they must supply.

title: Traffic intensity


text:
Transceiver

In radio communication, a transceiver is an electronic device which is a combination of a radio transmitter and a receiver, hence the name. It can both transmit and receive radio waves using an antenna, for communication purposes. These two related functions are often combined in a single device to reduce manufacturing costs. The term is also used for other devices which can both transmit and receive through a communications channel, such as optical transceivers which transmit and receive light in optical fiber systems, and bus transceivers which transmit and receive digital data in computer data buses.

Radio transceivers are widely used in wireless devices. One large use is in two-way radios, which are audio transceivers used for bidirectional person-to-person voice communication. Examples are cell phones, which transmit and receive the two sides of a phone conversation using radio waves to a cell tower, cordless phones in which both the phone handset and the base station have transceivers to communicate both sides of the conversation, and land mobile radio systems like walkie-talkies and CB radios. Another large use is in wireless modems in mobile networked computer devices such laptops, pads, and cellphones, which both transmit digital data to and receive data from a wireless router. Aircraft carry automated microwave transceivers called transponders which, when they are triggered by microwaves from an air traffic control radar, transmit a coded signal back to the radar to identify the aircraft. Satellite transponders in communication satellites receive digital telecommunication data from a satellite ground station, and retransmit it to another ground station.

History
The transceiver first appeared in the 1920s. Before then, receivers and transmitters were manufactured separately and devices that wanted to receive and transmit data required both components. Almost all amateur radio equipment today uses transceivers, but there is an active market for pure radio receivers, which are mainly used by shortwave listening operators.

Analog
Analog transceivers use frequency modulation to send and receive data. Although this technique limits the complexity of the data that can be broadcast, analog transceivers operate very reliably and are used in many emergency communication systems. They are also cheaper than digital transceivers, which makes them popular with the CB and HAM radio communities.

Digital
Digital transceivers send and receive binary data over radio waves. This allows more types of data to be broadcast, including video and encrypted communication, which is commonly used by police and fire departments. Digital transmissions tend to be clearer and more detailed than their analog counterparts. Many modern wireless devices operate on digital transmissions.

Telephony

In a wired telephone, the handset contains the transmitter (for speaking) and receiver (for listening). Despite being able to transmit and receive data, the whole unit is colloquially referred to as a "receiver". On a mobile telephone or other radiotelephone, the entire unit is a transceiver for both audio and radio.

A cordless telephone uses an audio and radio transceiver for the handset, and a radio transceiver for the base station. If a speakerphone is included in a wired telephone base or in a cordless base station, the base also becomes an audio transceiver.

A modem is similar to a transceiver in that it sends and receives a signal, but a modem uses modulation and demodulation. It modulates the signal being transmitted and demodulates the signal being received.

Ethernet
Transceivers are called Medium Attachment Units (MAUs) in IEEE 802.3 documents and were widely used in 10BASE2 and 10BASE5 Ethernet networks. Fiber-optic gigabit, 10 Gigabit Ethernet, 40 Gigabit Ethernet, and 100 Gigabit Ethernet utilize GBIC, SFP, SFP+, QSFP, XFP, XAUI, CXP, and CFP transceiver systems.

Regulation
Because transceivers are capable of broadcasting information over airwaves, they are required to adhere to various regulations. In the United States, the Federal Communications Commission oversees their use. Transceivers must meet certain standards and capabilities depending on their intended use, and manufacturers must comply with these requirements. However, transceivers can be modified by users to violate FCC regulations. For instance, they might be used to broadcast on a frequency or channel that they should not have access to. For this reason, the FCC monitors not only the production but also the use of these devices.

External articles

 * , John Stone Stone, "Apparatus for simultaneously transmitting and receiving space telegraph signals"
 * 7 MHz SSB transceiver

title: Transceiver


text:
Transmission

Transmit or Transmission may refer to:

Medicine, science and technology

 * Power transmission
 * Electric power transmission
 * Transmission (mechanical device), technology that allows controlled application of power
 * Automatic transmission
 * Manual transmission
 * Signal transmission, the process of sending and propagating an analogue or digital information signal
 * Analogue transmission - the process of sending and propagating an analogue signal
 * Data transmission, the process of sending and propagating digital information
 * Signaling (telecommunications) - transmission of meta-information related to the actual transmission
 * Monetary transmission mechanism, process by which asset prices and general economic conditions are affected as a result of monetary policy decisions
 * Pathogen transmission, the passing of a disease from an infected host individual or group to a particular individual or group
 * Cellular signaling - transmission of signals within or between living cells
 * Transmission in genetics, known otherwise as heredity, the transfer of genetic information from genes to another generation
 * Transmission (BitTorrent client), a free, open-source and cross-platform BitTorrent client application

Music

 * TRNSMT, music festival in Glasgow, Scotland
 * Transmission (band), an English experimental/post-rock band
 * Transmission (festival), an annual trance music event
 * Transmission Communications, an Australian record label

Albums

 * Transmission (Gay Dad album) or the title song, 2001
 * Transmission (The Tea Party album) or the title song, 1997
 * Transmission (Violent Delight album) or the title song, 2003
 * Transmissions (Alan Silva and Oluyemi Thomas album), 1993
 * Transmissions (Juno Reactor album), 1993
 * Transmissions (Starset album), 2014
 * Transmissions (Amos Lee album), 2024
 * Transmission (Low EP), 1996
 * Transmission (Mêlée EP), 2001

Songs

 * "Transmission" (song), by Joy Division, 1979
 * "Transmission", a mashup by Neil Cicierega from Mouth Silence, 2014
 * "Transmissions", a song by the American band Bright from The Albatross Guest House, 1997
 * "Transmissions', a song by the Irish band God Is an Astronaut from Origins, 2013

Other media

 * Transmission (magazine), a UK literary magazine
 * Transmission (novel), a 2005 novel by Hari Kunzru
 * Transmission (TV programme), a British music programme
 * Transmission, a webcomic by Mark A. Smith, former cartoonist for The Space Gypsy Adventures

Other uses

 * Transmission (esotericism)

title: Transmission


text:
Transmission block

In telecommunication, the term transmission block has the following meanings:

 * 1) A group of characters or bits transmitted as a block, unit, message, or packet. It usually includes additional encoded characters for error detection and correction.
 * 2) In data transmission, a group of records sent, processed, or recorded as a unit.

Some protocols require each transmission block to end with an end-of-message marker. This is often a control character such as End-of-Text (ETX), End-of-Transmission-Block (ETB), or End-of-Transmission (EOT).

Some protocols (especially those requiring ETX) require each transmission block to begin with a Start-of-Text character (STX).

title: Transmission block


text:
Transmission level point

In telecommunication, a transmission level point (TLP) is a test point in an electronic circuit that is typically a transmission channel. At the TLP, a test signal may be introduced or measured. Various parameters, such as the power of the signal, noise, voltage levels, wave forms, may be measured at the TLP.

The nominal transmission level at a TLP is a function of system design and is an expression of the design gain or attenuation (loss).

Voice-channel transmission levels at test points are measured in decibel-milliwatts (dBm) at a frequency of ~1000 hertz.

The dBm is an absolute reference level measurement (see ) with respect to 1 mW power. When the nominal signal power is 0 dBm at the TLP, the test point is called a zero transmission level point, or zero-dBm TLP. The abbreviation dBm0 stands for the power in dBm measured at a zero transmission level point. The TLP is thus characterized by the relation:

 * TLP = dBm — dBm0

The term TLP is commonly used as if it were a unit, preceded by the nominal level for the test point. For example, the expression 0 TLP refers to a 0  dBm  TLP. If for instance a signal is specified as -13 dBm0 at a particular point and -6 dBm is measured at that point, the TLP is +7 TLP.

The level at a TLP where an end instrument, such as a telephone set, is connected is usually specified as 0 dBm.

title: Transmission level point