text:
Group delay and phase delay

In signal processing, group delay and phase delay are two related ways of describing how a signal's frequency components are delayed in time when passing through a linear time-invariant (LTI) system (such as a microphone, coaxial cable, amplifier, loudspeaker, telecommunications system, ethernet cable, digital filter, or analog filter). Phase delay describes the time shift of a sinusoidal component (a sine wave in steady state). Group delay describes the time shift of the envelope of a wave packet, a "pack" or "group" of oscillations centered around one frequency that travel together, formed for instance by multiplying (amplitude modulation) a sine wave by an envelope (such as a tapering function).

These delays are usually frequency dependent, which means that different frequency components experience different delays. As a result, the signal's waveform experiences distortion as it passes through the system. This distortion can cause problems such as poor fidelity in analog video and analog audio, or a high bit-error rate in a digital bit stream. However, for the ideal case of a constant group delay across the entire frequency range of a bandlimited signal and flat frequency response, the waveform will experience no distortion.

Frequency components of a signal
Fourier analysis reveals how signals in time can alternatively be expressed as the sum of sinusoidal frequency components, each based on the trigonometric function $$\sin(x)$$ with a fixed amplitude and phase and no beginning and no end.

Linear time-invariant systems process each sinusoidal component independently; the property of linearity means they satisfy the superposition principle.

Introduction
The group delay and phase delay properties of a linear time-invariant (LTI) system are functions of frequency, giving the time from when a frequency component of a time varying physical quantity—for example a voltage signal—appears at the LTI system input, to the time when a copy of that same frequency component—perhaps of a different physical phenomenon—appears at the LTI system output.

A varying phase response as a function of frequency, from which group delay and phase delay can be calculated, typically occurs in devices such as microphones, amplifiers, loudspeakers, magnetic recorders, headphones, coaxial cables, and antialiasing filters. All frequency components of a signal are delayed when passed through such devices, or when propagating through space or a medium, such as air or water.

While a phase response describes phase shift in angular units (such as degrees or radians), the phase delay is in units of time and equals the negative of the phase shift at each frequency divided by the value of that frequency. Group delay is the negative derivative of phase shift with respect to frequency.

Phase delay
A linear time-invariant system or device has a phase response property and a phase delay property, where one can be calculated exactly from the other. Phase delay directly measures the device or system time delay of individual sinusoidal frequency components in the steady state. If the phase delay function at any given frequency—within a frequency range of interest—has the same constant of proportionality between the phase at a selected frequency and the selected frequency itself, the system/device will have the ideal of linear phase, which results in a constant group delay. Since phase delay is a function of frequency giving time delay, a departure from the flatness of its function graph can reveal time delay differences among the various signal frequency components, in which case those differences will contribute to signal distortion, which is manifested as the output signal waveform shape being different from that of the input signal.

Group delay
While phase delay describes the system's response to steady state sinusoidal components, group delay describes the response to amplitude modulated sinusoids.

The group delay is a convenient measure of the linearity of the phase with respect to frequency in a modulation system. For a modulation signal (passband signal), the information carried by the signal is carried exclusively in the wave envelope. Group delay therefore operates only with the frequency components derived from the envelope.

Basic modulation system

A device's group delay can be exactly calculated from the device's phase response, but not the other way around.

The simplest use case for group delay is illustrated in Figure 1 which shows a conceptual modulation system, which is itself an LTI system with a baseband output that is ideally an accurate copy of the baseband signal input. This system as a whole is referred to here as the outer LTI system/device, which contains an inner (red block) LTI system/device. As is often the case for a radio system, the inner red LTI system in Fig 1 can represent two LTI systems in cascade, for example an amplifier driving a transmitting antenna at the sending end and the other an antenna and amplifier at the receiving end.

Amplitude Modulation
Amplitude modulation creates the passband signal by shifting the baseband frequency components to a much higher frequency range. Although the frequencies are different, the passband signal carries the same information as the baseband signal. The demodulator does the inverse, shifting the passband frequencies back down to the original baseband frequency range. Ideally, the output (baseband) signal is a time delayed version of the input (baseband) signal where the waveform shape of the output is identical to that of the input.

In Figure 1, the outer system phase delay is the meaningful performance metric. For amplitude modulation, the inner red LTI device group delay becomes the outer LTI device phase delay. If the inner red device group delay is completely flat in the frequency range of interest, the outer device will have the ideal of a phase delay that is also completely flat, where the contribution of distortion due to the outer LTI device's phase response—determined entirely by the inner device's possibly different phase response—is eliminated. In that case, the group delay of the inner red device and the phase delay of the outer device give the same time delay figure for the signal as a whole, from the baseband input to the baseband output. It is significant to note that it is possible for the inner (red) device to have a very non-flat phase delay (but flat group delay), while the outer device has the ideal of a perfectly flat phase delay. This is fortunate because in LTI device design, a flat group delay is easier to achieve than a flat phase delay.

Angle Modulation
In an angle-modulation system—such as with frequency modulation (FM) or phase modulation (PM)—the (FM or PM) passband signal applied to an LTI system input can be analyzed as two separate passband signals, an in-phase (I) amplitude modulation AM passband signal and a quadrature-phase (Q) amplitude modulation AM passband signal, where their sum exactly reconstructs the original angle-modulation (FM or PM) passband signal. While the (FM/PM) passband signal is not amplitude modulation, and therefore has no apparent outer envelope, the I and Q passband signals do indeed have amplitude modulation envelopes. (However, unlike with regular amplitude modulation, the I and Q envelopes do not resemble the wave shape of the baseband signals, even though 100 percent of the baseband signal is represented in a complex manner by their envelopes.) So, for each of the I and Q passband signals, a flat group delay ensures that neither the I pass band envelope nor the Q passband envelope will have wave shape distortion, so when the I passband signal and the Q passband signal is added back together, the sum is the original FM/PM passband signal, which will also be unaltered.

Theory
According to LTI system theory (used in control theory and digital or analog signal processing), the output signal $$\displaystyle y(t)$$ of an LTI system can be determined by convoluting the time-domain impulse response $$\displaystyle h(t)$$ of the LTI system with the input signal $$\displaystyle x(t)$$. expresses this relationship as:

 * $$ y(t) = (h*x)(t) \mathrel{\stackrel{\text{def}}{=}} \int_{-\infty}^\infty h(t - \tau) \, x(\tau) \, \mathrm{d} \tau \mathrel{\stackrel{\text{def}}{=}} \mathcal{L}^{-1}\{H(s) \, X(s)\} \,, $$

where $$*$$ denotes the convolution operation, $$\displaystyle X(s)$$ and $$\displaystyle H(s)$$ are the Laplace transforms of the input $$\displaystyle x(t)$$ and impulse response $$\displaystyle h(t)$$, respectively, $s$ is the complex frequency, and $$\mathcal{L}^{-1}$$ is the inverse Laplace transform. $$\displaystyle H(s)$$ is called the transfer function of the LTI system and, like the impulse response $$\displaystyle h(t)$$, fully defines the input-output characteristics of the LTI system. This convolution can be evaluated by using the integral expression in the time domain, or (according to the rightmost expression) by using multiplication in the Laplace domain and then applying the inverse transform to return to time domain.

LTI system response to wave packet
Suppose that such a system is driven by a wave packet formed by a sinusoid multiplied by an amplitude envelope $$\displaystyle A_\text{env}(t)>0$$, so the input $$\displaystyle x(t)$$ can be expressed in the following form:

 * $$ x(t) = A_\text{env}(t) \cos(\omega t + \theta) \, . $$

Also suppose that the envelope $$\displaystyle A_\text{env}(t)$$ is slowly changing relative to the sinusoid's frequency $$\displaystyle \omega$$. This condition can be expressed mathematically as:

 * $$ \left| \frac{d}{dt} \log \big( A_\text{env}(t) \big) \right| \ll \omega \ .$$

Applying the earlier convolution equation would reveal that the output of such an LTI system is very well approximated as:

 * $$ y(t) = \big| H(i \omega) \big| \ A_\text{env}(t - \tau_g) \cos \big( \omega (t - \tau_\phi) + \theta \big) \; .$$

Here $$\displaystyle \tau_g$$ is the group delay and $$\displaystyle \tau_\phi$$ is the phase delay, and they are given by the expressions below (and potentially are functions of the angular frequency $$\displaystyle \omega$$). The phase of the sinusoid, as indicated by the positions of the zero crossings, is delayed in time by an amount equal to the phase delay, $$\displaystyle \tau_\phi$$. The envelope of the sinusoid is delayed in time by the group delay, $$\displaystyle \tau_g$$.

Mathematical definition of group delay and phase delay
The group delay, $$\displaystyle \tau_g$$, and phase delay, $$\displaystyle \tau_\phi$$, are (potentially) frequency-dependent and can be computed from the unwrapped phase shift $$\displaystyle \phi( \omega )$$. The phase delay at each frequency equals the negative of the phase shift at that frequency divided by the value of that frequency:

 * $$ \tau_\phi(\omega) = - \frac{\phi(\omega)}{\omega} \, . $$

The group delay at each frequency equals the negative of the slope (i.e. the derivative with respect to frequency) of the phase at that frequency:
 * $$ \tau_g(\omega) = - \frac{d \phi(\omega)}{d \omega} \, . $$

In a linear phase system (with non-inverting gain), both $$\displaystyle \tau_g$$ and $$\displaystyle \tau_\phi$$ are constant (i.e., independent of $$\displaystyle \omega$$) and equal, and their common value equals the overall delay of the system; and the unwrapped phase shift of the system (namely $$\displaystyle -\omega \tau_\phi$$) is negative, with magnitude increasing linearly with frequency $$\displaystyle \omega$$.

LTI system response to complex sinusoid
More generally, it can be shown that for an LTI system with transfer function $$\displaystyle H(s)$$ driven by a complex sinusoid of unit amplitude,

 * $$ x(t) = e^{i \omega t} \ $$

the output is

 * $$ \begin{align}

y(t) & = H(i \omega) \ e^{i \omega t} \ \\ & = \left( \big| H(i \omega) \big| e^{i \phi(\omega)} \right) \ e^{i \omega t} \ \\ & = \big| H(i \omega) \big| \ e^{i \left(\omega t + \phi(\omega) \right)} \ \\ \end{align} \ $$

where the phase shift $$\displaystyle \phi$$ is

 * $$ \phi(\omega) \ \stackrel{\mathrm{def}}{=}\ \arg \left\{ H(i \omega) \right\} \;. $$

1st order low- or high-pass RC filter example
The phase of a 1st-order low-pass filter formed by a RC circuit with cutoff frequency $$ \omega_o {=} \frac{1}{RC} $$ is:

$$ \phi(\omega) = -\arctan(\frac{\omega}{\omega_o}) \,. $$

Similarly, the phase for a 1st-order RC high-pass filter is:

$$ \phi(\omega) = \frac{\pi}{2} -\arctan(\frac{\omega}{\omega_o}) \,. $$

Taking the negative derivative with respect to $$ \omega $$ for either this low-pass or high-pass filter yields the same group delay of:

$$ \begin{align} \tau_g(\omega) &= \frac{\omega_o}{\omega^2 + \omega_o^2} \,. \\ \end{align} $$

For frequencies significantly lower than the cutoff frequency, the phase response is approximately linear (arctan for small inputs can be approximated as a line), so the group delay simplifies to a constant value of:

$$ \begin{align} \tau_g(\omega \ll \omega_o) &\approx \frac{1}{\omega_o} = RC \,. \\ \end{align} $$

Similarly, right at the cutoff frequency, $$ \tau_g(\omega {=} \omega_o) = \frac{1}{2 \omega_o} = \frac{RC}{2} \,. $$

As frequencies get even larger, the group delay decreases with the inverse square of the frequency and approaches zero as frequency approaches infinity.

Negative group delay
Filters will have negative group delay over frequency ranges where its phase response is positively-sloped. If a signal is band-limited within some maximum frequency B, then it is predictable to a small degree (within time periods smaller than $1⁄RC$). A filter whose group delay is negative over that signal's entire frequency range is able to use the signal's predictability to provide an illusion of a non-causal time advance. However, if the signal contains an unpredictable event (such as an abrupt change which makes the signal's spectrum exceed its band-limit), then the illusion breaks down. Circuits with negative group delay (e.g., Figure 2) are possible, though causality is not violated.

Negative group delay filters can be made in both digital and analog domains. Applications include compensating for the inherent delay of low-pass filters, to create zero phase filters, which can be used to quickly detect changes in the trends of sensor data or stock prices.

Group delay in audio
Group delay has some importance in the audio field and especially in the sound reproduction field. Many components of an audio reproduction chain, notably loudspeakers and multiway loudspeaker crossover networks, introduce group delay in the audio signal. It is therefore important to know the threshold of audibility of group delay with respect to frequency,  especially if the audio chain is supposed to provide high fidelity reproduction. The best thresholds of audibility table has been provided by Blauert and Laws.

Flanagan, Moore and Stone conclude that at 1, 2 and 4 kHz, a group delay of about 1.6 ms is audible with headphones in a non-reverberant condition. Other experimental results suggest that when the group delay in the frequency range from 300 Hz to 1 kHz is below 1.0 ms, it is inaudible.

The waveform of any signal can be reproduced exactly by a system that has a flat frequency response and group delay over the bandwidth of the signal. Leach introduced the concept of differential time-delay distortion, defined as the difference between the phase delay and the group delay:

 * $$ \Delta\tau = \tau_\phi - \tau_g $$.

An ideal system should exhibit zero or negligible differential time-delay distortion.

It is possible to use digital signal processing techniques to correct the group delay distortion that arises due to the use of crossover networks in multi-way loudspeaker systems. This involves considerable computational modeling of loudspeaker systems in order to successfully apply delay equalization, using the Parks-McClellan FIR equiripple filter design algorithm.

Group delay in optics
Group delay is important in physics, and in particular in optics.

In an optical fiber, group delay is the transit time required for optical power, traveling at a given mode's group velocity, to travel a given distance. For optical fiber dispersion measurement purposes, the quantity of interest is group delay per unit length, which is the reciprocal of the group velocity of a particular mode. The measured group delay of a signal through an optical fiber exhibits a wavelength dependence due to the various dispersion mechanisms present in the fiber.

It is often desirable for the group delay to be constant across all frequencies; otherwise there is temporal smearing of the signal. Because group delay is $ \tau_g(\omega) = -\frac{d\phi}{d\omega}$, it therefore follows that a constant group delay can be achieved if the transfer function of the device or medium has a linear phase response (i.e., $$\phi(\omega) = \phi(0) - \tau_g \omega $$ where the group delay $$\tau_g $$ is a constant). The degree of nonlinearity of the phase indicates the deviation of the group delay from a constant value.

The differential group delay is the difference in propagation time between the two eigenmodes X and Y polarizations. Consider two eigenmodes that are the 0° and 90° linear polarization states. If the state of polarization of the input signal is the linear state at 45° between the two eigenmodes, the input signal is divided equally into the two eigenmodes. The power of the transmitted signal ET,total is the combination of the transmitted signals of both x and y modes.

 * $$E_T =  (E_{i,x} \cdot t_x)^2 + (E_{i,y} \cdot t_y)^2 \, $$

The differential group delay Dt is defined as the difference in propagation time between the eigenmodes: Dt = |tt,x − tt,y|.

True time delay
A transmitting apparatus is said to have true time delay (TTD) if the time delay is independent of the frequency of the electrical signal. TTD allows for a wide instantaneous signal bandwidth with virtually no signal distortion such as pulse broadening during pulsed operation.

TTD is an important characteristic of lossless and low-loss, dispersion free, transmission lines. reveals that signals propagate through them at a speed of $$1 / \sqrt{LC}$$ for a distributed inductance $1⁄B$ and capacitance $L$. Hence, any signal's propagation delay through the line simply equals the length of the line divided by this speed.

Group delay from transfer function polynomials
If a transfer function or Sij of a scattering parameter, is in a polynomial Laplace transform form, then the mathematical definition for group delay above may be solved analytically in closed form. A polynomial transfer function $$P(S)$$ may be taken along the $$j\omega$$ axis and defined as $$P(j\omega)$$. $$\phi(\omega)$$ may be determined from $$P(j\omega)$$, and then the group delay may be determined by solving for $$-d\phi(\omega)|/d\omega$$.

to determine $$\phi(\omega)$$ from $$P(j\omega)$$, use the definition of $$\phi(\omega) = tan^{-1}(P(j\omega)_{imag}/P(j\omega)_{real})$$. Given that $$j^{2N}$$ is always real, and $$j^{2N+1}$$is always imaginary, $$\phi(\omega)$$ may be redefined as $$\phi(\omega) = tan^{-1}(-jP(j\omega)_{odd}/P(j\omega)_{even})$$ where even and odd refer to the polynomials that contain only the even or odd order coefficients respectively. The $$-j$$ in the numerator merely converts the imaginary $$P(j\omega)_{odd}$$ numerator to a real value, since $$P(j\omega)_{odd}$$ by itself is purely imaginary.

$$\begin{align} &\frac{dtan^{-1}(f(x))}{dx} = \frac{df(x)/dx}{1+f(x)^2} \\ &f(x) = \frac{-jP(j\omega)_{odd}}{P(j\omega)_{even}} \\ &\frac{df(x)}{dx} = \frac{P(j\omega)_{even} \frac{d(P(j\omega)_{odd})}{dx} - -jP(j\omega)_{odd} \frac{d(-jP(j\omega)_{even})}{dx}} {P(j\omega)_{even}^2} \end{align}$$

The above expressions contain four terms to calculate:

$$\begin{array}{lcl} Se = P(j\omega)_{even} &=& \sum_{k=0}^{N/2}P_{2k}(j\omega)^{2k} &=& \sum_{k=0}^{N/2}P_{2k}(-1)^{k}(\omega)^{2k}\\ So = P(j\omega)_{odd} &=& -j\sum_{k=1}^{(N+1)/2}P_{2k-1}(j\omega)^{2k-1} &=& \sum_{k=1}^{(N+1)/2}P_{2k-1}(-1)^{k-1}(\omega)^{2k-1}\\ De = \frac{d(P(j\omega)_{even})}{dx} &=& -j\sum_{k=1}^{N/2}2kP_{2k}(j\omega)^{2k-1} &=& \sum_{k=1}^{N/2}2kP_{2k}(-1)^{k-1}(\omega)^{2k-1} \\ Do = \frac{d(P(j\omega)_{odd})}{dx} &=& \sum_{k=1}^{(N+1)/2}{(2k-1)}P_{2k-1}(j\omega)^{2k-2} &=& \sum_{k=1}^{(N+1)/2}{(2k-1)}P_{2k-1}(-1)^{k-1}(\omega)^{2k-2}\\ \\ \frac{df(x)}{dx} &=& \frac{SeDo - SoDe}{Se^2} \end{array}$$

The equations above may be used to determine the group delay of polynomial $$P(S)$$ in closed form, shown below after the equations have been reduced to a simplified form.

$$\text{Group Delay} =gd(P(j\omega))= -\frac{d\phi(\omega)}{d\omega} = -\frac {(So*De + Se*Do)} {(Se^2 + So^2)} \text{ sec}$$

Polynomial ratio
A polynomial ratio of the form $$P2(S) = P_{num}(S)/P_{den}(S)$$, such as that typically found in the definition of filter designs, may have the group delay determined by taking advantage of the phase relation, $$\phi(P1/P2) = \phi(P1) - \phi(P2)$$.

$$\text{Group Delay} = gd(P2) = gd(P2_{num}) - gd(P2_{den}) sec$$

Simple filter example
A four pole Legendre filter transfer function used in the Legendre filter example is shown below.

$$T_4(j\omega) = \frac{1}{2.4494897(j\omega)^4 + 3.8282201(j\omega)^3 + 4.6244874(j\omega)^2 + 3.0412127(j\omega) + 1}$$

The numerator group delay by inspection is zero, so only the denominator group delay need be determined.

$$\begin{align} &Pe_{den} = 2.4494897\omega^4 - 4.6244874\omega^2 + 1  \\ &Po_{den} = -3.8282201\omega^3 + 3.0412127\omega       \\ &De_{den} = 4(2.4494897)\omega^3 - 2(4.6244874)\omega \\ &Do_{den} = 3(-3.8282201)\omega^2 + 3.0412127 \end{align}$$

Evaluating at $$\omega$$ = 1 rad/sec:

$$\begin{align} &Pe_{den} = -1.1749977 \\ &Po_{den} = -0.7870074      \\ &De_{den} = -0.548984 \\ &Do_{den} = -8.4434476 \end{align}$$

$$\begin{align} &\text{Group Delay} =gd(T_4(j\omega))= -\frac{d\phi(\omega)}{d\omega} \\ &= \bigg[0--\frac {((-0.7870074*-0.548984) + (-1.1749977*-8.4434476))} {((-1.1749977)^2 + (-0.7870074)^2)}\bigg]  \\ &= 5.1765430\text{ sec} \\ &\text{at }\omega = 1\text{ rad/sec} \end{align}$$

The group delay calculation procedure and results may be confirmed to be correct by comparing them to the results derived from the digital derivative of the phase angle, $$\phi(\omega)$$, using a small delta $$\Delta\omega$$ of +/-1.e-04 rad/sec.

$$\begin{align} &\text{Group Delay} =gd(T_4(j\omega))= -\frac{d\phi(\omega)}{d\omega} \\ &= - (\phi(1+1e-04)-\phi(1.-1e04))/2e-04\\

&= 5.1765432\text{ sec} \\ &\text{at }\omega = 1\text{ rad/sec} \end{align}$$

Since the group delay calculated by the digital derivative using a small delta is within 7 digits of accuracy when compared to the precise analytical calculation, the group delay calculation procedure and results are confirmed to be correct.

Deviation from Linear Phase
Deviation from Linear Phase, $$\phi_{DLP}(\omega)$$, sometimes referred to as just, "phase deviation", is the difference between the phase response, $$\phi(\omega)$$, and the linear portion of the phase response $$\phi_L(\omega)$$, and is a useful measurement to determine the linearity of $$\phi(\omega)$$.

A convenient means to measure $$\phi_{DLP}(\omega)$$ is to take the simple linear regression of $$\phi(\omega)$$ sampled over a frequency range of interest, and subtract it from the actual $$\phi(\omega)$$. The $$\phi_{DLP}(\omega)$$ of an ideal linear phase response would be expected to have a value of 0 across the frequency range of interest (such as the pass band of a filter), while the $$\phi_{DLP}(\omega)$$ of a real-world approximately linear phase response may deviate from 0 by a small finite amount across the frequency range of interest.

Advantage over group delay
An advantage of measuring or calculating $$\phi_{DLP}(\omega)$$ over measuring or calculating group delay, $$gd(\omega)$$, is $$\phi_{DLP}(\omega)$$ always converges to 0 as the phase becomes linear, whereas $$gd(\omega)$$ converges on a finite quantity that may not be known ahead of time. Given this, a linear phase optimizing function may more easily be executed with a $$\phi_{DLP}(\omega){=}0$$ goal than with a $$gd(\omega){=}constant$$ goal when the value for $$constant$$ is not necessarily already known.

title: Group delay and phase delay


text:
Guided ray

A guided ray (also bound ray or trapped ray) is a ray of light in a multi-mode optical fiber, which is confined by the core.

For step index fiber, light entering the fiber will be guided if it falls within the acceptance cone of the fiber, that is if it makes an angle with the fiber axis that is less than the acceptance angle,

 * $$\theta < \arcsin \left( \sqrt{n_0^2 - n_\mathrm{c}^2} \right)$$ ,

where
 * θ is the angle the ray makes with the fiber axis, before entering the fiber,
 * n0 is the refractive index along the central axis (core) of the fiber, and
 * nc is the refractive index of the cladding.

The quantity $$\sin \theta$$ is the numerical aperture of the fiber. The quantity $$2 \theta$$ is sometimes called the total acceptance angle of the fiber.

This result can be derived from Snell's law by considering the critical angle. Light that enters the core with an angle below the acceptance angle strikes the core-cladding boundary at an angle above the critical angle, and experiences total internal reflection. This repeats on every bounce within the fiber core, and so the light is confined to the core. The confinement of light by the fiber can also be described in terms of bound modes or guided modes. This treatment is necessary when considering single-mode fiber, since the ray model does not accurately describe the propagation of light in this type of fiber.

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

title: Guided ray


text:
Hagelbarger code

In telecommunication, a Hagelbarger code is a convolutional code that enables error bursts to be corrected provided that there are relatively long error-free intervals between the error bursts.

In the Hagelbarger code, inserted parity check bits are spread out in time so that an error burst is not likely to affect more than one of the groups in which parity is checked.

title: Hagelbarger code


text:
Halftone characteristic

In a facsimile system the halftone characteristic is either:
 * 1) the relationship between the density of the recorded copy and the density of the original, or
 * 2) the relationship between the amplitude of the facsimile signal to either the density of the object or the density of the recorded copy when only a portion of the system is under consideration.  In an FM facsimile system, an appropriate parameter other than the amplitude is used.

title: Halftone characteristic


text:
Hamming code

In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data.

In mathematical terms, Hamming codes are a class of binary linear code. For each integer $$ there is a code-word with block length $2^{r} − 1$ and message length $r ≥ 2$. Hence the rate of Hamming codes is $2^{r} − r − 1$, which is the highest possible for codes with minimum distance of three (i.e., the minimal number of bit changes needed to go from any code word to any other code word is three) and block length $1 − r⁄(2^{r} − 1)$. The parity-check matrix of a Hamming code is constructed by listing all columns of length $3$ that are non-zero, which means that the dual code of the Hamming code is the shortened Hadamard code, also known as a Simplex code. The parity-check matrix has the property that any two columns are pairwise linearly independent.

Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (usually RAM), where bit errors are extremely rare and Hamming codes are widely used, and a RAM with this correction system is an ECC RAM (ECC memory). In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one-bit error occurs and when any two-bit errors occur. In this sense, extended Hamming codes are single-error correcting and double-error detecting, abbreviated as SECDED.

History
Richard Hamming, the inventor of Hamming codes, worked at Bell Labs in the late 1940s on the Bell Model V computer, an electromechanical relay-based machine with cycle times in seconds. Input was fed in on punched paper tape, seven-eighths of an inch wide, which had up to six holes per row. During weekdays, when errors in the relays were detected, the machine would stop and flash lights so that the operators could correct the problem. During after-hours periods and on weekends, when there were no operators, the machine simply moved on to the next job.

Hamming worked on weekends, and grew increasingly frustrated with having to restart his programs from scratch due to detected errors. In a taped interview, Hamming said, "And so I said, 'Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?'". Over the next few years, he worked on the problem of error-correction, developing an increasingly powerful array of algorithms. In 1950, he published what is now known as Hamming code, which remains in use today in applications such as ECC memory.

Codes predating Hamming
A number of simple error-detecting codes were used before Hamming codes, but none were as effective as Hamming codes in the same overhead of space.

Parity
Parity adds a single bit that indicates whether the number of ones (bit-positions with values of one) in the preceding data was even or odd. If an odd number of bits is changed in transmission, the message will change parity and the error can be detected at this point; however, the bit that changed may have been the parity bit itself. The most common convention is that a parity value of one indicates that there is an odd number of ones in the data, and a parity value of zero indicates that there is an even number of ones. If the number of bits changed is even, the check bit will be valid and the error will not be detected.

Moreover, parity does not indicate which bit contained the error, even when it can detect it. The data must be discarded entirely and re-transmitted from scratch. On a noisy transmission medium, a successful transmission could take a long time or may never occur. However, while the quality of parity checking is poor, since it uses only a single bit, this method results in the least overhead.

Two-out-of-five code
A two-out-of-five code is an encoding scheme which uses five bits consisting of exactly three 0s and two 1s. This provides $$\binom{5}{3}=10$$ possible combinations, enough to represent the digits 0–9. This scheme can detect all single bit-errors, all odd numbered bit-errors and some even numbered bit-errors (for example the flipping of both 1-bits). However it still cannot correct any of these errors.

Repetition
Another code in use at the time repeated every data bit multiple times in order to ensure that it was sent correctly. For instance, if the data bit to be sent is a 1, an n = 3 repetition code will send 111. If the three bits received are not identical, an error occurred during transmission. If the channel is clean enough, most of the time only one bit will change in each triple. Therefore, 001, 010, and 100 each correspond to a 0 bit, while 110, 101, and 011 correspond to a 1 bit, with the greater quantity of digits that are the same ('0' or a '1') indicating what the data bit should be. A code with this ability to reconstruct the original message in the presence of errors is known as an error-correcting code. This triple repetition code is a Hamming code with m = 2, since there are two parity bits, and 22 − 2 − 1 = 1 data bit.

Such codes cannot correctly repair all errors, however. In our example, if the channel flips two bits and the receiver gets 001, the system will detect the error, but conclude that the original bit is 0, which is incorrect. If we increase the size of the bit string to four, we can detect all two-bit errors but cannot correct them (the quantity of parity bits is even); at five bits, we can both detect and correct all two-bit errors, but not all three-bit errors.

Moreover, increasing the size of the parity bit string is inefficient, reducing throughput by three times in our original case, and the efficiency drops drastically as we increase the number of times each bit is duplicated in order to detect and correct more errors.

Description
If more error-correcting bits are included with a message, and if those bits can be arranged such that different incorrect bits produce different error results, then bad bits could be identified. In a seven-bit message, there are seven possible single bit errors, so three error control bits could potentially specify not only that an error occurred but also which bit caused the error.

Hamming studied the existing coding schemes, including two-of-five, and generalized their concepts. To start with, he developed a nomenclature to describe the system, including the number of data bits and error-correction bits in a block. For instance, parity includes a single bit for any data word, so assuming ASCII words with seven bits, Hamming described this as an (8,7) code, with eight bits in total, of which seven are data. The repetition example would be (3,1), following the same logic. The code rate is the second number divided by the first, for our repetition example, 1/3.

Hamming also noticed the problems with flipping two or more bits, and described this as the "distance" (it is now called the Hamming distance, after him). Parity has a distance of 2, so one bit flip can be detected but not corrected, and any two bit flips will be invisible. The (3,1) repetition has a distance of 3, as three bits need to be flipped in the same triple to obtain another code word with no visible errors. It can correct one-bit errors or it can detect - but not correct - two-bit errors. A (4,1) repetition (each bit is repeated four times) has a distance of 4, so flipping three bits can be detected, but not corrected. When three bits flip in the same group there can be situations where attempting to correct will produce the wrong code word. In general, a code with distance k can detect but not correct k − 1 errors.

Hamming was interested in two problems at once: increasing the distance as much as possible, while at the same time increasing the code rate as much as possible. During the 1940s he developed several encoding schemes that were dramatic improvements on existing codes. The key to all of his systems was to have the parity bits overlap, such that they managed to check each other as well as the data.

General algorithm
The following general algorithm generates a single-error correcting (SEC) code for any number of bits. The main idea is to choose the error-correcting bits such that the index-XOR (the XOR of all the bit positions containing a 1) is 0. We use positions 1, 10, 100, etc. (in binary) as the error-correcting bits, which guarantees it is possible to set the error-correcting bits so that the index-XOR of the whole message is 0. If the receiver receives a string with index-XOR 0, they can conclude there were no corruptions, and otherwise, the index-XOR indicates the index of the corrupted bit.

An algorithm can be deduced from the following description:

 * 1) Number the bits starting from 1: bit 1, 2, 3, 4, 5, 6, 7, etc.
 * 2) Write the bit numbers in binary:  1, 10, 11, 100, 101, 110, 111, etc.
 * 3) All bit positions that are powers of two (have a single 1 bit in the binary form of their position) are parity bits: 1, 2, 4, 8, etc. (1, 10, 100, 1000)
 * 4) All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
 * 5) Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.
 * 6) Parity bit 1 covers all bit positions which have the least significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.
 * 7) Parity bit 2 covers all bit positions which have the second least significant bit set: bits 2-3, 6-7, 10-11, etc.
 * 8) Parity bit 4 covers all bit positions which have the third least significant bit set: bits 4–7, 12–15, 20–23, etc.
 * 9) Parity bit 8 covers all bit positions which have the fourth least significant bit set: bits 8–15, 24–31, 40–47, etc.
 * 10) In general each parity bit covers all bits where the bitwise AND of the parity position and the bit position is non-zero.

If a byte of data to be encoded is 10011010, then the data word (using _ to represent the parity bits) would be __1_001_1010, and the code word is 011100101010.

The choice of the parity, even or odd, is irrelevant but the same choice must be used for both encoding and decoding.

This general rule can be shown visually:

 * {| class="wikitable" style="text-align:center;"

!colspan="2"| Bit position ! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16 !! 17 !! 18 !! 19 !! 20 !colspan="2"| Encoded data bits !style="background-color: #90FF90;"| p1 !style="background-color: #90FF90;"| p2 !! d1 !style="background-color: #90FF90;"| p4 !! d2 !! d3 !! d4 !style="background-color: #90FF90;"| p8 !! d5 !! d6 !! d7 !! d8 !! d9 !! d10 !! d11 !style="background-color: #90FF90;"| p16 !! d12 !! d13 !! d14 !! d15 !rowspan="5"|Parity bit coverage !style="background-color: #90FF90;"| p1 !style="background-color: #90FF90;"| p2 !style="background-color: #90FF90;"| p4 !style="background-color: #90FF90;"| p8 !style="background-color: #90FF90;"| p16
 * rowspan="7"| ...
 * }
 * }

Shown are only 20 encoded bits (5 parity, 15 data) but the pattern continues indefinitely. The key thing about Hamming Codes that can be seen from visual inspection is that any given bit is included in a unique set of parity bits. To check for errors, check all of the parity bits. The pattern of errors, called the error syndrome, identifies the bit in error. If all parity bits are correct, there is no error. Otherwise, the sum of the positions of the erroneous parity bits identifies the erroneous bit. For example, if the parity bits in positions 1, 2 and 8 indicate an error, then bit 1+2+8=11 is in error. If only one parity bit indicates an error, the parity bit itself is in error.

With $m$ parity bits, bits from 1 up to $$2^m-1$$ can be covered. After discounting the parity bits, $$2^m-m-1$$ bits remain for use as data. As $m$ varies, we get all the possible Hamming codes:

Hamming codes with additional parity (SECDED)
Hamming codes have a minimum distance of 3, which means that the decoder can detect and correct a single error, but it cannot distinguish a double bit error of some codeword from a single bit error of a different codeword. Thus, some double-bit errors will be incorrectly decoded as if they were single bit errors and therefore go undetected, unless no correction is attempted.

To remedy this shortcoming, Hamming codes can be extended by an extra parity bit. This way, it is possible to increase the minimum distance of the Hamming code to 4, which allows the decoder to distinguish between single bit errors and two-bit errors. Thus the decoder can detect and correct a single error and at the same time detect (but not correct) a double error.

If the decoder does not attempt to correct errors, it can reliably detect triple bit errors. If the decoder does correct errors, some triple errors will be mistaken for single errors and "corrected" to the wrong value. Error correction is therefore a trade-off between certainty (the ability to reliably detect triple bit errors) and resiliency (the ability to keep functioning in the face of single bit errors).

This extended Hamming code was popular in computer memory systems, starting with IBM 7030 Stretch in 1961, where it is known as SECDED (or SEC-DED, abbreviated from single error correction, double error detection). Server computers in 21st century, while typically keeping the SECDED level of protection, no longer use the Hamming's method, relying instead on the designs with longer codewords (128 to 256 bits of data) and modified balanced parity-check trees. The (72,64) Hamming code is still popular in some hardware designs, including Xilinx FPGA families.

[7,4] Hamming code

In 1950, Hamming introduced the [7,4] Hamming code. It encodes four data bits into seven bits by adding three parity bits. As explained earlier, it can either detect and correct single-bit errors or it can detect (but not correct) both single and double-bit errors.

With the addition of an overall parity bit, it becomes the [8,4] extended Hamming code which is SECDED and can both detect and correct single-bit errors and detect (but not correct) double-bit errors.

Construction of G and H
The matrix $$\mathbf{G} := \begin{pmatrix} \begin{array}{c|c} I_k & -A^\text{T} \\ \end{array} \end{pmatrix}$$ is called a (canonical) generator matrix of a linear (n,k) code,

and $$\mathbf{H} := \begin{pmatrix} \begin{array}{c|c} A & I_{n-k} \\ \end{array} \end{pmatrix}$$ is called a parity-check matrix.

This is the construction of G and H in standard (or systematic) form. Regardless of form, G and H for linear block codes must satisfy

$$\mathbf{H}\,\mathbf{G}^\text{T} = \mathbf{0}$$, an all-zeros matrix.

Since [7, 4, 3] = [n, k, d] = [2m − 1, 2m − 1 − m, 3]. The parity-check matrix H of a Hamming code is constructed by listing all columns of length m that are pair-wise independent.

Thus H is a matrix whose left side is all of the nonzero n-tuples where order of the n-tuples in the columns of matrix does not matter. The right hand side is just the (n − k)-identity matrix.

So G can be obtained from H by taking the transpose of the left hand side of H with the identity k-identity matrix on the left hand side of G.

The code generator matrix $$\mathbf{G}$$ and the parity-check matrix $$\mathbf{H}$$ are:

$$\mathbf{G} := \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}_{4,7}$$

and

$$\mathbf{H} := \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}_{3,7}.$$

Finally, these matrices can be mutated into equivalent non-systematic codes by the following operations:

 * Column permutations (swapping columns)
 * Elementary row operations (replacing a row with a linear combination of rows)

Encoding

 * Example

From the above matrix we have 2k = 24 = 16 codewords. Let $$\vec{a}$$ be a row vector of binary data bits, $$ \vec{a}=[a_1,a_2,a_3,a_4],\quad a_i\in \{0,1\} $$. The codeword $$\vec{x}$$ for any of the 16 possible data vectors $$ \vec{a} $$ is given by the standard matrix product $$\vec{x}=\vec{a}G $$ where the summing operation is done modulo-2.

For example, let $$\vec{a}=[1,0,1,1]$$. Using the generator matrix $$G$$ from above, we have (after applying modulo 2, to the sum),

$$\vec{x}=\vec{a}G= \begin{pmatrix} 1 & 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 & 1 & 2 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 1 & 0 \end{pmatrix}$$

[8,4] Hamming code with an additional parity bit

The [7,4] Hamming code can easily be extended to an [8,4] code by adding an extra parity bit on top of the (7,4) encoded word (see Hamming(7,4)). This can be summed up with the revised matrices:

 * $$\mathbf{G} := \begin{pmatrix}

1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}_{4,8}$$

and

\mathbf{H} := \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}_{4,8} .$$

Note that H is not in standard form. To obtain G, elementary row operations can be used to obtain an equivalent matrix to H in systematic form:

\mathbf{H} = \left( \begin{array}{cccc|cccc} 0 & 1 & 1 & 1 &  1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1  &  0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1  &  0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0  &  0 & 0 & 0 & 1 \end{array} \right)_{4,8} .$$

For example, the first row in this matrix is the sum of the second and third rows of H in non-systematic form. Using the systematic construction for Hamming codes from above, the matrix A is apparent and the systematic form of G is written as

\mathbf{G} = \left( \begin{array}{cccc|cccc} 1 & 0 & 0 & 0 &  0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0  &  1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0  &  1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1  &  1 & 1 & 1 & 0 \end{array} \right)_{4,8} .$$

The non-systematic form of G can be row reduced (using elementary row operations) to match this matrix.

The addition of the fourth row effectively computes the sum of all the codeword bits (data and parity) as the fourth parity bit.

For example, 1011 is encoded (using the non-systematic form of G at the start of this section) into 01 1 0 011 0 where blue digits are data; red digits are parity bits from the [7,4] Hamming code; and the green digit is the parity bit added by the [8,4] code. The green digit makes the parity of the [7,4] codewords even.

Finally, it can be shown that the minimum distance has increased from 3, in the [7,4] code, to 4 in the [8,4] code. Therefore, the code can be defined as [8,4] Hamming code.

To decode the [8,4] Hamming code, first check the parity bit. If the parity bit indicates an error, single error correction (the [7,4] Hamming code) will indicate the error location, with "no error" indicating the parity bit. If the parity bit is correct, then single error correction will indicate the (bitwise) exclusive-or of two error locations. If the locations are equal ("no error") then a double bit error either has not occurred, or has cancelled itself out. Otherwise, a double bit error has occurred.

title: Hamming code


text:
Hamming distance

In information theory, the Hamming distance between two strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or equivalently, the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming.

A major application is in coding theory, more specifically to block codes, in which the equal-length strings are vectors over a finite field.

Definition
The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different.

Examples
The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the Hamming distance between:
 * "kain" and  "kain"  is 3.
 * "krin" and  "krin"  is 3.
 * "kin" and  "kin"  is 4.
 * ' and  ' is 4.
 * 2396 and  2396  is 3.

Properties
For a fixed length n, the Hamming distance is a metric on the set of the words of length n (also known as a Hamming space), as it fulfills the conditions of non-negativity, symmetry, the Hamming distance of two words is 0 if and only if the two words are identical, and it satisfies the triangle inequality as well: Indeed, if we fix three words a, b and c, then whenever there is a difference between the ith letter of a and the ith letter of c, then there must be a difference between the ith letter of a and ith letter of b, or between the ith letter of b and the ith letter of c. Hence the Hamming distance between a and c is not larger than the sum of the Hamming distances between a and b and between b and c. The Hamming distance between two words a and b can also be seen as the Hamming weight of a − b for an appropriate choice of the − operator, much as the difference between two integers can be seen as a distance from zero on the number line.

For binary strings a and b the Hamming distance is equal to the number of ones (population count) in a XOR b. The metric space of length-n binary strings, with the Hamming distance, is known as the Hamming cube; it is equivalent as a metric space to the set of distances between vertices in a hypercube graph. One can also view a binary string of length n as a vector in $$\mathbb{R}^{n}$$ by treating each symbol in the string as a real coordinate; with this embedding, the strings form the vertices of an n-dimensional hypercube, and the Hamming distance of the strings is equivalent to the Manhattan distance between the vertices.

Error detection and error correction
The minimum Hamming distance or minimum distance (usually denoted by dmin) is used to define some essential notions in coding theory, such as error detecting and error correcting codes. In particular, a code C is said to be k error detecting if, and only if, the minimum Hamming distance between any two of its codewords is at least k+1.

For example, consider a code consisting of two codewords "000" and "111". The Hamming distance between these two words is 3, and therefore it is k=2 error detecting. This means that if one bit is flipped or two bits are flipped, the error can be detected. If three bits are flipped, then "000" becomes "111" and the error cannot be detected.

A code C is said to be k-error correcting if, for every word w in the underlying Hamming space H, there exists at most one codeword c (from C) such that the Hamming distance between w and c is at most k. In other words, a code is k-errors correcting if the minimum Hamming distance between any two of its codewords is at least 2k+1. This is also understood geometrically as any closed balls of radius k centered on distinct codewords being disjoint. These balls are also called Hamming spheres in this context.

For example, consider the same 3-bit code consisting of the two codewords "000" and "111". The Hamming space consists of 8 words 000, 001, 010, 011, 100, 101, 110 and 111. The codeword "000" and the single bit error words "001","010","100" are all less than or equal to the Hamming distance of 1 to "000". Likewise, codeword "111" and its single bit error words "110","101" and "011" are all within 1 Hamming distance of the original "111". In this code, a single bit error is always within 1 Hamming distance of the original codes, and the code can be 1-error correcting, that is k=1. Since the Hamming distance between "000" and "111" is 3, and those comprise the entire set of codewords in the code, the minimum Hamming distance is 3, which satisfies 2k+1 = 3.

Thus a code with minimum Hamming distance d between its codewords can detect at most d-1 errors and can correct ⌊(d-1)/2⌋ errors. The latter number is also called the packing radius or the error-correcting capability of the code.

History and applications
The Hamming distance is named after Richard Hamming, who introduced the concept in his fundamental paper on Hamming codes, Error detecting and error correcting codes, in 1950. Hamming weight analysis of bits is used in several disciplines including information theory, coding theory, and cryptography.

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

The Hamming distance is also used in systematics as a measure of genetic distance.

However, for comparing strings of different lengths, or strings where not just substitutions but also insertions or deletions have to be expected, a more sophisticated metric like the Levenshtein distance is more appropriate.

Algorithm example
The following function, written in Python 3, returns the Hamming distance between two strings:

Or, in a shorter expression:

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

where the zip function merges two equal-length collections in pairs.

The following C function will compute the Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The running time of this procedure is proportional to the Hamming distance rather than to the number of bits in the inputs. It computes the bitwise exclusive or of the two inputs, and then finds the Hamming weight of the result (the number of nonzero bits) using an algorithm of that repeatedly finds and clears the lowest-order nonzero bit. Some compilers support the __builtin_popcount function which can calculate this using specialized processor hardware where available.

A faster alternative is to use the population count (popcount) assembly instruction. Certain compilers such as GCC and Clang make it available via an intrinsic function:

title: Hamming distance


text:
Handshake (computing)

In computing, a handshake is a signal between two devices or programs, used to, e.g., authenticate, coordinate. An example is the handshaking between a hypervisor and an application in a guest virtual machine.

In telecommunications, a handshake is an automated process of negotiation between two participants (example "Alice and Bob") through the exchange of information that establishes the protocols of a communication link at the start of the communication, before full communication begins. The handshaking process usually takes place in order to establish rules for communication when a computer attempts to communicate with another device. Signals are usually exchanged between two devices to establish a communication link. For example, when a computer communicates with another device such as a modem, the two devices will signal each other that they are switched on and ready to work, as well as to agree to which protocols are being used.

Handshaking can negotiate parameters that are acceptable to equipment and systems at both ends of the communication channel, including information transfer rate, coding alphabet, parity, interrupt procedure, and other protocol or hardware features. Handshaking is a technique of communication between two entities. However, within TCP/IP RFCs, the term "handshake" is most commonly used to reference the TCP three-way handshake. For example, the term "handshake" is not present in RFCs covering FTP or SMTP. One exception is Transport Layer Security, TLS, setup, FTP RFC 4217. In place of the term "handshake", FTP RFC 3659 substitutes the term "conversation" for the passing of commands.

A simple handshaking protocol might only involve the receiver sending a message meaning "I received your last message and I am ready for you to send me another one." A more complex handshaking protocol might allow the sender to ask the receiver if it is ready to receive or for the receiver to reply with a negative acknowledgement meaning "I did not receive your last message correctly, please resend it" (e.g., if the data was corrupted en route).

Handshaking facilitates connecting relatively heterogeneous systems or equipment over a communication channel without the need for human intervention to set parameters.

TCP three-way handshake
Establishing a normal TCP connection requires three separate steps:
 * The first host (Alice) sends the second host (Bob) a "synchronize" (SYN) message with its own sequence number $$x$$, which Bob receives.
 * Bob replies with a synchronize-acknowledgment (SYN-ACK) message with its own sequence number $$y$$ and acknowledgement number $$x + 1$$, which Alice receives.
 * Alice replies with an acknowledgment (ACK) message with acknowledgement number $$y + 1$$, which Bob receives and to which he doesn't need to reply.
 * In this setup, the synchronize messages act as service requests from one server to the other, while the acknowledgement messages return to the requesting server to let it know the message was received.

The reason for the client and server not using a default sequence number such as 0 for establishing the connection is to protect against two incarnations of the same connection reusing the same sequence number too soon, which means a segment from an earlier incarnation of a connection might interfere with a later incarnation of the connection.

SMTP
The Simple Mail Transfer Protocol (SMTP) is the key Internet standard for email transmission. It includes handshaking to negotiate authentication, encryption and maximum message size.

TLS handshake
When a Transport Layer Security (SSL or TLS) connection starts, the record encapsulates a "control" protocol—the handshake messaging protocol (content type 22). This protocol is used to exchange all the information required by both sides for the exchange of the actual application data by TLS. It defines the messages formatting or containing this information and the order of their exchange. These may vary according to the demands of the client and server—i.e., there are several possible procedures to set up the connection. This initial exchange results in a successful TLS connection (both parties ready to transfer application data with TLS) or an alert message (as specified below).

The protocol is used to negotiate the secure attributes of a session. (RFC 5246, p. 37)

WPA2 wireless
The WPA2 standard for wireless uses a four-way handshake defined in IEEE 802.11i-2004.

Dial-up access modems
One classic example of handshaking is that of dial-up modems, which typically negotiate communication parameters for a brief period when a connection is first established, and there after use those parameters to provide optimal information transfer over the channel as a function of its quality and capacity. The "squealing" (which is actually a sound that changes in pitch 100 times every second) noises made by some modems with speaker output immediately after a connection is established are in fact the sounds of modems at both ends engaging in a handshaking procedure; once the procedure is completed, the speaker might be silenced, depending on the settings of operating system or the application controlling the modem.

Serial "Hardware Handshaking"
This frequently used term describes the use of RTS and CTS signals over a serial interconnection. It is, however, not quite correct; it's not a true form of handshaking, and is better described as flow control.

Mobile device charging
In mobile device chargers offering special quick-charge abilities to supported devices, the charging process will switch up to a higher output voltage for increased power transfer. But this could cause serious damage to an unsupported device or even result in a fire. It is therefore very important for the device and charger to first perform a handshake to "agree" on mutually supported charge parameters. If such a charger can't identify the connected device or determine its compatibility, it will default to normal but much slower charge parameters within the USB standard.

title: Handshake (computing)


text:
Hard copy

In information handling, the U.S. Federal Standard 1037C (Glossary of Telecommunication Terms) defines a hard copy as a permanent reproduction, or copy, in the form of a physical object, of any media suitable for direct use by a person (in particular paper), of displayed or transmitted data. Examples of hard copies include teleprinter pages, continuous printed tapes, computer printouts, and radio photo prints. On the other hand, physical objects such as magnetic tapes, floppy disks, or non-printed punched paper tapes are not defined as hard copies by 1037C.

A file that can be viewed without printing on a screen is sometimes called a soft copy. The U.S. Federal Standard 1037C defines "soft copy" as "a nonpermanent display image, for example, a cathode ray tube display."

The term "hard copy" predates the digital computer. In the book and newspaper printing process, "hard copy" refers to a manuscript or typewritten document that has been edited and proofread and is ready for typesetting or being read on-air in a radio or television broadcast. The old meaning of hard copy was mostly discarded after the information revolution.

Use in computer security
One often-overlooked use for printers is in the field of IT security. Copies of various system and server activity logs are typically stored on the local filesystem, where a remote attacker – having achieved their primary goals – can then alter or delete the contents of the logs in an attempt to "cover their tracks" or otherwise thwart the efforts of system administrators and security experts. However, if the log entries are simultaneously given to a printer, line-by-line, a local hard-copy record of system activity is created – which cannot be remotely altered or otherwise manipulated. Dot matrix printers are ideal for this task, as they can sequentially print each log entry, one at a time, as they are added to the log. The usual dot-matrix printer support for continuous stationery also prevents incriminating pages from being surreptitiously removed or altered without evidence of tampering.

"Dead-tree" dysphemism
The hacker's Jargon File defines a dead-tree version to be a paper version of an online document, where "dead trees" refer to paper.

A saying from the Jargon File is that "You can't grep dead trees", which comes from the Unix command grep, which searches the contents of text files. This means that there is an advantage to keeping documents in digital form, rather than on paper, so that they can be more easily searched for specific contents. A similarly entry in the Jargon File is "tree-killer", which may refer either to a printer or a person who wastes paper.

Dead-tree edition refers to a printed paper version of a written work, as opposed to digital alternatives such as a web page.

title: Hard copy


text:
Hard sectoring

Hard sectoring in a magnetic or optical data storage device is a form of sectoring which uses a physical mark or hole in the recording medium to reference sector locations.

In older 8- and 51⁄4-inch floppy disks, hard sectoring was implemented by punching sector holes in the disk to mark the start of each sector. These were equally spaced holes, at a common radius. This was in addition to the index hole, situated between two sector holes, to mark the start of the entire track of sectors. When the index or sector hole was recognized by an optical sensor, a sector signal was generated. Timing electronics or software would use the faster timing of the index hole between sector holes, to generate an index signal. Data read and write is faster in this technique than soft sectoring as no operations are to be performed regarding the starting and ending points of tracks.

Storage formats using hard sectoring

 * 32 sector 8-inch floppy disks
 * 10 sector and 16 sector 51⁄4-inch floppy disks
 * Numerous magneto-optical formats
 * DVD-RAM

title: Hard sectoring


text:
Harmonic

In physics, acoustics, and telecommunications, a harmonic is a sinusoidal wave with a frequency that is a positive integer multiple of the fundamental frequency of a periodic signal. The fundamental frequency is also called the 1st harmonic; the other harmonics are known as higher harmonics. As all harmonics are periodic at the fundamental frequency, the sum of harmonics is also periodic at that frequency. The set of harmonics forms a harmonic series.

The term is employed in various disciplines, including music, physics, acoustics, electronic power transmission, radio technology, and other fields. For example, if the fundamental frequency is 50 Hz, a common AC power supply frequency, the frequencies of the first three higher harmonics are 100 Hz (2nd harmonic), 150 Hz (3rd harmonic), 200 Hz (4th harmonic) and any addition of waves with these frequencies is periodic at 50 Hz.

"An nth characteristic mode, for n > 1, will have nodes that are not vibrating. For example, the 3rd characteristic mode will have nodes at $\tfrac{1}{3}$L and $\tfrac{2}{3}$L, where L is the length of the string. In fact, each nth characteristic mode, for n not a multiple of 3, will not have nodes at these points. These other characteristic modes will be vibrating at the positions $\tfrac{1}{3}$L and $\tfrac{2}{3}$L. If the player gently touches one of these positions, then these other characteristic modes will be suppressed. The tonal harmonics from these other characteristic modes will then also be suppressed. Consequently, the tonal harmonics from the nth characteristic modes, where n is a multiple of 3, will be made relatively more prominent."

In music, harmonics are used on string instruments and wind instruments as a way of producing sound on the instrument, particularly to play higher notes and, with strings, obtain notes that have a unique sound quality or "tone colour". On strings, bowed harmonics have a "glassy", pure tone. On stringed instruments, harmonics are played by touching (but not fully pressing down the string) at an exact point on the string while sounding the string (plucking, bowing, etc.); this allows the harmonic to sound, a pitch which is always higher than the fundamental frequency of the string.

Terminology
Harmonics may be called "overtones", "partials", or "upper partials", and in some music contexts, the terms "harmonic", "overtone" and "partial" are used fairly interchangeably. But more precisely, the term "harmonic" includes all pitches in a harmonic series (including the fundamental frequency) while the term "overtone" only includes pitches above the fundamental.

Characteristics
"A whizzing, whistling tonal character, distinguishes all the harmonics both natural and artificial from the firmly stopped intervals; therefore their application in connection with the latter must always be carefully considered. — Richard Scholz (c. 1888-1912)"

Most acoustic instruments emit complex tones containing many individual partials (component simple tones or sinusoidal waves), but the untrained human ear typically does not perceive those partials as separate phenomena. Rather, a musical note is perceived as one sound, the quality or timbre of that sound being a result of the relative strengths of the individual partials. Many acoustic oscillators, such as the human voice or a bowed violin string, produce complex tones that are more or less periodic, and thus are composed of partials that are nearly matched to the integer multiples of fundamental frequency and therefore resemble the ideal harmonics and are called "harmonic partials" or simply "harmonics" for convenience (although it's not strictly accurate to call a  partial  a  harmonic,  the first being actual and the second being theoretical).

Oscillators that produce harmonic partials behave somewhat like one-dimensional resonators, and are often long and thin, such as a guitar string or a column of air open at both ends (as with the metallic modern orchestral transverse flute). Wind instruments whose air column is open at only one end, such as trumpets and clarinets, also produce partials resembling harmonics. However they only produce partials matching the odd harmonics—at least in theory. In practical use, no real acoustic instrument behaves as perfectly as the simplified physical models predict; for example, instruments made of non-linearly elastic wood, instead of metal, or strung with gut instead of brass or steel strings, tend to have not-quite-integer partials.

Partials whose frequencies are not integer multiples of the fundamental are referred to as inharmonic partials. Some acoustic instruments emit a mix of harmonic and inharmonic partials but still produce an effect on the ear of having a definite fundamental pitch, such as pianos, strings plucked pizzicato, vibraphones, marimbas, and certain pure-sounding bells or chimes. Antique singing bowls are known for producing multiple harmonic partials or multiphonics. Other oscillators, such as cymbals, drum heads, and most percussion instruments, naturally produce an abundance of inharmonic partials and do not imply any particular pitch, and therefore cannot be used melodically or harmonically in the same way other instruments can.

Building on of Sethares (2004), dynamic tonality introduces the notion of pseudo-harmonic partials, in which the frequency of each partial is aligned to match the pitch of a corresponding note in a pseudo-just tuning, thereby maximizing the consonance of that pseudo-harmonic timbre with notes of that pseudo-just tuning.

Partials, overtones, and harmonics
An overtone is any partial higher than the lowest partial in a compound tone. The relative strengths and frequency relationships of the component partials determine the timbre of an instrument. The similarity between the terms overtone and partial sometimes leads to their being loosely used interchangeably in a musical context, but they are counted differently, leading to some possible confusion. In the special case of instrumental timbres whose component partials closely match a harmonic series (such as with most strings and winds) rather than being inharmonic partials (such as with most pitched percussion instruments), it is also convenient to call the component partials "harmonics", but not strictly correct, because harmonics are numbered the same even when missing, while partials and overtones are only counted when present. This chart demonstrates how the three types of names (partial, overtone, and harmonic) are counted (assuming that the harmonics are present):

In many musical instruments, it is possible to play the upper harmonics without the fundamental note being present. In a simple case (e.g., recorder) this has the effect of making the note go up in pitch by an octave, but in more complex cases many other pitch variations are obtained. In some cases it also changes the timbre of the note. This is part of the normal method of obtaining higher notes in wind instruments, where it is called overblowing. The extended technique of playing multiphonics also produces harmonics. On string instruments it is possible to produce very pure sounding notes, called harmonics or flageolets by string players, which have an eerie quality, as well as being high in pitch. Harmonics may be used to check at a unison the tuning of strings that are not tuned to the unison. For example, lightly fingering the node found halfway down the highest string of a cello produces the same pitch as lightly fingering the node $n$ of the way down the second highest string. For the human voice see Overtone singing, which uses harmonics.

While it is true that electronically produced periodic tones (e.g. square waves or other non-sinusoidal waves) have "harmonics" that are whole number multiples of the fundamental frequency, practical instruments do not all have this characteristic. For example, higher "harmonics" of piano notes are not true harmonics but are "overtones" and can be very sharp, i.e. a higher frequency than given by a pure harmonic series. This is especially true of instruments other than strings, brass, or woodwinds. Examples of these "other" instruments are xylophones, drums, bells, chimes, etc.; not all of their overtone frequencies make a simple whole number ratio with the fundamental frequency. (The fundamental frequency is the reciprocal of the longest time period of the collection of vibrations in some single periodic phenomenon. )

On stringed instruments
"Harmonics may be singly produced [on stringed instruments] (1) by varying the point of contact with the bow, or (2) by slightly pressing the string at the nodes, or divisions of its aliquot parts ($\tfrac{\ 1\ }{2}$, $\tfrac{\ 1\ }{3}$, $\tfrac{\ 1\ }{4}$, etc.). (1) In the first case, advancing the bow from the usual place where the fundamental note is produced, towards the bridge, the whole scale of harmonics may be produced in succession, on an old and highly resonant instrument. The employment of this means produces the effect called 'sul ponticello.' (2) The production of harmonics by the slight pressure of the finger on the open string is more useful. When produced by pressing slightly on the various nodes of the open strings they are called 'natural harmonics'. ... Violinists are well aware that the longer the string in proportion to its thickness, the greater the number of upper harmonics it can be made to yield."

- Grove's Dictionary of Music and Musicians (1879)

The following table displays the stop points on a stringed instrument at which gentle touching of a string will force it into a harmonic mode when vibrated. String harmonics (flageolet tones) are described as having a "flutelike, silvery quality" that can be highly effective as a special color or tone color (timbre) when used and heard in orchestration. It is unusual to encounter natural harmonics higher than the fifth partial on any stringed instrument except the double bass, on account of its much longer strings.

 * {| class="wikitable"

! Harmonic ! Stop note ! Note sounded (relative to open string) !width="50"| Audio frequency (Hz) !width="50"| Cents above fundamental (offset by octave) ! Audio (octave shifted)
 * style="text-align:center;"| 1
 * fundamental, perfect unison
 * style="text-align:center;"| P1
 * style="text-align:right;"| 600
 * style="text-align:right;"| 0.0
 * style="text-align:center;"| 2
 * first perfect octave
 * style="text-align:center;"| P8
 * style="text-align:right;"| 1,200
 * style="text-align:right;"| 0.0
 * style="text-align:center;"| 3
 * perfect fifth
 * style="text-align:center;"| P8 + P5
 * style="text-align:right;"| 1,800
 * style="text-align:right;"| 702.0
 * style="text-align:center;"| 4
 * doubled perfect octave
 * style="text-align:center;"| 2·P8
 * style="text-align:right;"| 2,400
 * style="text-align:right;"| 0.0
 * style="text-align:center;"| 5
 * just major third, major third
 * style="text-align:center;"| 2·P8 + M3
 * style="text-align:right;"| 3,000
 * style="text-align:right;"| 386.3
 * style="text-align:center;"| 6
 * perfect fifth
 * style="text-align:center;"| 2·P8 + P5
 * style="text-align:right;"| 3,600
 * style="text-align:right;"| 702.0
 * style="text-align:center;"| 7
 * harmonic seventh, septimal minor seventh (‘the lost chord’)
 * style="text-align:center;"| 2·P8 + m7↓
 * style="text-align:right;"| 4,200
 * style="text-align:right;"| 968.8
 * style="text-align:center;"| 8
 * third perfect octave
 * style="text-align:center;"| 3·P8
 * style="text-align:right;"| 4,800
 * style="text-align:right;"| 0.0
 * style="text-align:center;"| 9
 * Pythagorean major second harmonic ninth
 * style="text-align:center;"| 3·P8 + M2
 * style="text-align:right;"| 5,400
 * style="text-align:right;"| 203.9
 * style="text-align:center;"| 10
 * just major third
 * style="text-align:center;"| 3·P8 + M3
 * style="text-align:right;"| 6,000
 * style="text-align:right;"| 386.3
 * style="text-align:center;"| 11
 * lesser undecimal tritone, undecimal semi-augmented fourth
 * style="text-align:center;"| 3·P8 + a4
 * style="text-align:right;"| 6,600
 * style="text-align:right;"| 551.3
 * style="text-align:center;"| 12
 * perfect fifth
 * style="text-align:center;"| 3·P8 + P5
 * style="text-align:right;"| 7,200
 * style="text-align:right;"| 702.0
 * style="text-align:center;"| 13
 * tridecimal neutral sixth
 * style="text-align:center;"| 3·P8 + n6↓
 * style="text-align:right;"| 7,800
 * style="text-align:right;"| 840.5
 * style="text-align:center;"| 14
 * harmonic seventh, septimal minor seventh (‘the lost chord’)
 * style="text-align:center;"| 3·P8 + m7⤈
 * style="text-align:right;"| 8,400
 * style="text-align:right;"| 968.8
 * style="text-align:center;"| 15
 * just major seventh
 * style="text-align:center;"| 3·P8 + M7
 * style="text-align:right;"| 9,000
 * style="text-align:right;"| 1,088.3
 * style="text-align:center;"| 16
 * fourth perfect octave
 * style="text-align:center;"| 4·P8
 * style="text-align:right;"| 9,600
 * style="text-align:right;"| 0.0
 * style="text-align:center;"| 17
 * septidecimal semitone
 * style="text-align:center;"| 4·P8 + m2⇟
 * style="text-align:right;"| 10,200
 * style="text-align:right;"| 105.0
 * style="text-align:center;"| 18
 * Pythagorean major second
 * style="text-align:center;"| 4·P8 + M2
 * style="text-align:right;"| 10,800
 * style="text-align:right;"| 203.9
 * style="text-align:center;"| 19
 * nanodecimal minor third
 * style="text-align:center;"| 4·P8 + m3
 * style="text-align:right;"| 11,400
 * style="text-align:right;"| 297.5
 * style="text-align:center;"| 20
 * just major third
 * style="text-align:center;"| 4·P8 + M3
 * style="text-align:right;"| 12,000
 * style="text-align:right;"| 386.3
 * }
 * style="text-align:center;"| 3·P8 + M7
 * style="text-align:right;"| 9,000
 * style="text-align:right;"| 1,088.3
 * style="text-align:center;"| 16
 * fourth perfect octave
 * style="text-align:center;"| 4·P8
 * style="text-align:right;"| 9,600
 * style="text-align:right;"| 0.0
 * style="text-align:center;"| 17
 * septidecimal semitone
 * style="text-align:center;"| 4·P8 + m2⇟
 * style="text-align:right;"| 10,200
 * style="text-align:right;"| 105.0
 * style="text-align:center;"| 18
 * Pythagorean major second
 * style="text-align:center;"| 4·P8 + M2
 * style="text-align:right;"| 10,800
 * style="text-align:right;"| 203.9
 * style="text-align:center;"| 19
 * nanodecimal minor third
 * style="text-align:center;"| 4·P8 + m3
 * style="text-align:right;"| 11,400
 * style="text-align:right;"| 297.5
 * style="text-align:center;"| 20
 * just major third
 * style="text-align:center;"| 4·P8 + M3
 * style="text-align:right;"| 12,000
 * style="text-align:right;"| 386.3
 * }
 * style="text-align:right;"| 11,400
 * style="text-align:right;"| 297.5
 * style="text-align:center;"| 20
 * just major third
 * style="text-align:center;"| 4·P8 + M3
 * style="text-align:right;"| 12,000
 * style="text-align:right;"| 386.3
 * }
 * style="text-align:right;"| 386.3
 * }
 * }

Artificial harmonics
Occasionally a score will call for an artificial harmonic, produced by playing an overtone on an already stopped string. As a performance technique, it is accomplished by using two fingers on the fingerboard, the first to shorten the string to the desired fundamental, with the second touching the node corresponding to the appropriate harmonic.

Other information
Harmonics may be either used in or considered as the basis of just intonation systems. Composer Arnold Dreyblatt is able to bring out different harmonics on the single string of his modified double bass by slightly altering his unique bowing technique halfway between hitting and bowing the strings. Composer Lawrence Ball uses harmonics to generate music electronically.

title: Harmonic


text:
H channel

In the Integrated Services Digital Network (ISDN), a high-speed communication channel comprising multiple aggregated low-speed channels to accommodate bandwidth-intensive applications such as file transfer, videoconferencing, and high-quality audio. An H channel is formed of multiple bearer B channels bonded together in a primary rate access (PRA) or primary rate interface (PRI) frame in support of applications with bandwidth requirements that exceed the B channel rate of 64 kbit/s. The channels, once bonded, remain so end-to-end, from transmitter to receiver, through the ISDN network. The feature is known variously as multirate ISDN, Nx64, channel aggregation, and bonding. H channels are implemented as:
 * H0 = 384 kbit/s(6 B channels)
 * H10 = 1472 kbit/s(23 B channels)
 * H11 = 1536 kbit/s(24 B channels)
 * H12 = 1920 kbit/s(30 B channels) – International (E-carrier) only.

title: H channel