Code encoding 2026-10-14
Code encoding maps messages injectively to codewords. For a dimension- linear code with generator matrix , the standard encoder maps to . The redundancy makes error detection and recovery possible; for a Reed-Solomon code, encoding can instead evaluate a message polynomial at the chosen field elements.
Dual code Created 2026-09-24 Updated 2026-11-05
For a linear code , the dual code is the orthogonal complement
under the standard bilinear bilinear form. If has dimension , the dual code has dimension and , because this bilinear form is nondegenerate.
The independent rows of a parity-check matrix for form a basis of , so that matrix is a generator matrix for the dual code. If a check matrix has redundant rows, its rows still span the dual code but are not themselves a basis. For example, the dual code of the length- binary even-weight binary code is the repetition code spanned by the all-one word.
The holding rate at state of a continuous-time Markov chain with generator matrix is
For a conservative chain with finite , its holding time has exponential distribution: and . Conditional on a jump, the next state is with probability . Thus the rate determines when departure occurs, while normalized outgoing rates determine where it goes.
If the outgoing rates are and for two distinct other states, the total rate is five, the mean holding time is , and departure chooses them with probabilities and . A zero rate gives an absorbing state with infinite holding time. Statewise finite rates alone do not rule out explosion of a continuous-time Markov chain.
Linear code Created 2026-09-24 Updated 2026-11-05
A linear code over a finite field is a linear subspace . Its parameters record word length, dimension, and minimum Hamming distance. For a nonzero code, is the least Hamming weight of a nonzero word, because the difference of two words is another word.
For example, is a binary code, the kernel of the parity-check matrix . Linearity lets a generator matrix encode messages and lets the parity-check syndrome detect corruption. The zero code needs a separate convention for its minimum distance, since it has no nonzero word.
A positive transition intensity can be modeled as . A unit increase in a fixed covariate multiplies the intensity by . A changing covariate generally gives a time-dependent generator matrix.
Panel-observed multi-state likelihood Created 2026-09-28 Updated 2026-11-05
For a time-homogeneous continuous-time Markov chain with generator matrix , let be its transition matrix. Conditional on a known state at time zero, a panel visit recording state at duration contributes to the likelihood. This transition probability sums over all intervening paths, including unobserved transitions.
An exact endpoint transition is a different observation. If the state immediately before the transition is known to be and the destination is , its time-density contribution is
For a small interval , this follows by multiplying the probability of being in just before by the transition probability . The relevant occupancy is the pre-event state , rather than the destination . If the record additionally establishes no transition at all before a first jump at , the contribution instead is .
For exact entry into an absorbing state when the immediately preceding state is hidden, sum over possible living states:
This is the mixed panel and exact-death likelihood contribution. Multiplying a panel destination probability by would generally confuse observation of the endpoint state with observation of a jump into it.
Parity-check matrix Created 2026-09-24 Updated 2026-11-05
For a linear code of dimension , a parity-check matrix is an matrix whose rows form a basis of the dual code . With codewords written as row vectors,
Thus gives a full set of independent linear equations defining . A received row vector has syndrome , which is zero exactly when is a codeword.
For example, defines the binary even-weight binary code of length . It has rank , so its kernel has dimension . One can also use a check matrix with redundant rows; the same kernel is defined, but only an independent row selection is a generator matrix whose rows form a basis of .
For a binary linear code , define the linear functional . This is the parity of the Hamming weight, so the even-weight subcode of a binary linear code is
If , then . Otherwise its image is all of , and rank-nullity theorem gives . The kernel of a linear map is a linear subspace, proving the required dichotomy including closure under addition.
Let be a full-rank generator matrix. Messages correspond bijectively to codewords . If the th column is nonzero, the coordinate is a nonzero linear functional. Choose with . Translation pairs the messages with coordinate zero and those with coordinate one, so exactly codewords contribute one at position . Summing over the columns proves the total weight of a full-support binary linear code formula
A zero column would contribute zero instead, explaining the hypothesis.
For the Hamming code, use a parity-check matrix whose columns are all nonzero vectors of , once each. Then and . The sum of all columns is zero: each coordinate occurs as one exactly times, which is even for . Consequently
Under this column labelling, the support of a vector of a codeword is identified with a set of distinct nonzero columns whose sum is zero. No one-column or two-column support of a vector has this property, confirming .
We can count the low-weight coefficients of a binary Hamming code directly. For weight three, choose ordered distinct nonzero columns in ways. The third must be , which is nonzero and different from both. Every unordered support of a vector has orderings, so .
For weight four, the first two columns are again distinct and nonzero. The third must avoid , giving possibilities. The fourth is ; it is nonzero because , and cannot equal any of the first three because those are distinct. Conversely every ordered zero-sum four-tuple arises in this way. Dividing by gives .
For weight five, the first three columns must be linearly independent. If , the sum condition would force the fourth and fifth to coincide. Thus there are choices for the first three. Put . The fourth column must avoid all seven nonzero vectors of their linear span: would repeat a column; would force the fifth column to be zero; and would force the fifth column to be , respectively. Conversely, if avoids these seven vectors, is nonzero and distinct from . This gives choices for and determines . Dividing by yields
At , the last count is zero, as the argument also shows.
The dual code is the row space of , so its codewords are for . For nonzero , the linear functional takes value one on exactly half the vectors of , by the same translation-pairing argument used above. Removing the zero vector removes only a zero value, so the Hamming weight is still . Since has matrix rank , distinct give distinct codewords. This proves the constant weight of a binary simplex code and its full distribution:
In particular, the ordinary weight enumerator of the binary simplex code is .
Apply the MacWilliams identity to this dual code, whose size is . For , the result is
The coefficient of in the second product is a value of the binary Kravchuk polynomials
These bounds merely enforce and . Since , they agree with the bounds in the PDF. Therefore the requested formula is
For a further check on the low-weight counts, gives
Thus , , and . Substituting these into the boxed formula and using reproduces the three direct combinatorial counts above.
Finally, at the only possible term in the defining sum has , so , because is even. Consequently
The unique length- binary word of weight is the all-ones word, exactly as proved by the parity-check matrix calculation.
Over a finite field , a linear code of length and dimension is a -dimensional subspace . A full-row-rank generator matrix gives , using row-vector messages. A full-row-rank parity-check matrix gives . The dual code is , of dimension . Thus the rows of span , and
Conversely the rank conditions and imply that the row space of equals the kernel of , by inclusion and equality of dimensions.
For a CSS code, specialize to binary linear codes , of dimensions . Define orthonormal encoded states
Different cosets have disjoint computational-basis support. Their span has dimension , so it encodes logical qubits. For binary vectors write and . The stabilizer generators are for a basis of , and for a basis of . They fix each encoded state: the former permute its coset terms and the latter contribute phases . Their commutation relation is , so the classical dual inclusion makes them commute. There are independent checks, giving precisely this encoded space.
For a Pauli error , the Z checks give bit-error syndrome , where checks , and the X checks give phase-error syndrome , where generates and hence checks . Classical decoders therefore correct up to bit flips and phase flips if and . A Y error has both components; it is not omitted from this correction scheme.
For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when , and is a stabilizer when ; a pure-Z error preserves it when , and is a stabilizer when . Consequently, for ,
A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least ; pure-X or pure-Z operators attain that minimum. Thus arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.
An explicit example is the Steane code. Take to be the binary Hamming code with
The distinct nonzero columns show that has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives , proving . Every nonzero word of has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of . A logical basis is the uniform superposition over and over , since . The resulting CSS code corrects every single-qubit error.
Use the time-homogeneous continuous-time multi-state model displayed in part ii. Write for the state at time , for its generator matrix, and
For , is the transition intensity, and . Condition on the observed initial state, and treat the clinic observation process and administrative end of follow-up as noninformative. A panel-observed interval contributes its transition probability, not the density of a jump at the examination date; the transitions inside that interval need not have been observed.
For the first patient, the two clinic intervals contribute . The subsequent death is observed at elapsed time after the last clinic state, so its contribution is the conditional death-time density
The equality uses the permitted directions: starting from state 3, only living states 3 and 4 can be occupied before death. To obtain this density directly, survival in a living state until time , followed by death in , has probability ; add over the unobserved state . Hence the mixed panel and exact-death likelihood contribution is
It includes the possibility of an unrecorded transition between the last clinic visit and death. Keeping only would exclude that allowed history, while would be the probability of death by that time rather than the density of death at that time. With dates recorded in whole days, an exact interval-likelihood treatment integrates this density over the relevant day; the density formulation is its fine-time approximation.
For the second patient, the three successive intervals with state 1 at both ends, then the interval ending in state 2, and the last interval remaining in state 2 give the panel-observed multi-state likelihood
There is no additional death contribution after the final administrative observation. Each likelihood contribution already accounts for being alive in the observed state at that visit. For independent patients their joint conditional likelihood contribution is .
For an explicit form, put . Irreversibility gives
and
These formulas follow by integrating the density of the one possible intermediate jump time; at equal exit rates the limiting expression is . Thus
Using the displayed fitted rates as numerical values gives per year, per year and , providing a check of the probability-versus-density distinction.
A binary block code of length is a nonempty subset . Its size is , the number of distinct codewords. The Hamming distance counts coordinates at which two words differ. The code's minimum Hamming distance is when there are at least two words. No pairwise minimum exists for a singleton code; it can be assigned as a convention when needed.
A binary linear code is a vector subspace of . If its dimension is , a generator matrix has a basis of as its rows, giving
To match the coordinate-row convention, take a parity-check matrix of size , with independent columns, and define
The transpose is the usual parity-check matrix with one column per coordinate. By rank-nullity theorem, the displayed kernel has dimension . The two constructions agree when : the generator's row space lies in the parity-check kernel and has the same dimension, hence equals it. Conversely, for a given , choose the columns of as a basis of its dual code ; orthogonality and the dimension formula give exactly as the kernel.
For a nonzero linear code, is a nonzero codeword whenever are distinct codewords, and . Conversely compare any nonzero codeword with zero. Thus the minimum Hamming distance of a linear code is the least nonzero Hamming weight.
Write for the row associated with coordinate . A nonzero binary vector is a codeword exactly when
Its nonzero coordinate positions therefore index a linearly dependent set of rows. Conversely, a dependence among a set of rows has coefficients in , not all zero; putting these coefficients in the corresponding coordinates gives a nonzero codeword of weight no greater than the number of rows in that set. Taking minima in both directions proves the parity-check dependencies determine minimum distance criterion:
Rows here are indexed by positions: equal row vectors at different positions are two distinct members of the indexed family. In the usual matrix convention, the same result refers to columns of . For the zero code, neither a nonzero codeword nor a dependent coordinate set exists, so both minima can consistently be interpreted as .
For the Hamming code, let , set , and let the rows of be all nonzero vectors of , each once. These rows include the standard basis, so has rank and the code has dimension and size . There is no dependence involving one row, because no row is zero, or two rows, because no rows are equal. For , any two distinct nonzero vectors have a distinct nonzero sum , which is another row. These three rows sum to zero. Thus for .
The perfectness of a Hamming code also has a direct decoding proof. Given any received word , its syndrome is . A zero syndrome means . Otherwise it equals exactly one row . The vector then has syndrome zero and is the unique codeword obtainable by changing one coordinate. There is no other codeword at distance at most one: its necessary correction would have to have the same syndrome, and among zero and all single-coordinate errors the syndromes are precisely the distinct vectors of . Therefore the radius-one Hamming balls about codewords partition .
Equivalently, each ball contains words; disjointness and show that none are uncovered. Hence every nondegenerate binary Hamming code is a perfect single-error-correcting code. For , the construction is the singleton code , whose one radius-one ball is also the whole ambient space. This deals with the degenerate boundary without falsely claiming its minimum distance is three.
Work over the finite field , and write for row of the PDF's matrix. The first row has Hamming weight eleven; all other rows have Hamming weight seven. To check their intersections economically, index the last eleven columns modulo eleven. The last eleven rows, after deleting the first column, are the successive cyclic shifts of the set . Direct calculation gives
The intersection sizes for equal those for . Thus two different rows among meet in four positions, including their shared first coordinate, whereas meets each of these rows in six positions. All these intersection sizes are even numbers, while each row weight is an odd number. Consequently . The first row and column agree, and the entry of the last eleven-by-eleven block depends only on the sum of its row and column indices modulo eleven, because successive rows are left shifts. Thus is a symmetric matrix, so .
The generator matrix has rank twelve, and
Hence its linear code lies in its dual code . Both have dimension twelve, so : it is a self-dual code. Moreover , and is an invertible matrix, so this is another generator matrix for the same code. In the column parity-check matrix convention of the question,
The matrix has rank twelve, so its nullspace condition characterizes exactly.
To prove the minimum Hamming distance, first observe that the rows of have Hamming weights twelve and eight. For binary vectors,
Every partial sum of generator rows is orthogonal to every further generator row, by . Its intersection with that row therefore contains an even number of positions. Induction using this identity proves that every codeword has weight divisible by four: is a doubly even code.
The systematic-matrix proof of extended Golay distance now excludes weight four. Write a codeword as and put . If its total weight were four, . For , the right half is a row of and has weight seven or eleven. For , the right half is the sum of two distinct rows; the intersection counts above give weight or . For , the right half would be a unit vector, but then would be a row of , of weight seven or eleven. For , the right half would vanish, contradicting invertibility of . Thus no nonzero word has weight four. Every nonzero weight is consequently at least eight, and any generator row other than the first attains eight. Since the minimum Hamming distance of a linear code is its least nonzero weight,
Define the length- binary Golay code as the punctured code obtained by deleting the first coordinate of this extended binary Golay code. This puncturing is injective on , because a nonzero word in its kernel would have weight one. Thus , and deleting one coordinate gives . The sum of the first two generator rows has weight eight and first coordinate one, so its puncture has weight seven. Therefore . In fact any coordinate can be punctured: every left coordinate except the first occurs in a weight-eight generator row, the first occurs in the sum just used, and every right coordinate occurs in at least one of the weight-eight generator rows.
The radius-three Hamming balls around the words of are disjoint, since two centers in intersecting balls would have Hamming distance at most six. Each ball contains
words. Their combined size is , the size of the entire binary Hamming space. Hence
For decoding in , write the received word as , where is the unknown error in its two halves. Its syndrome is
Let denote the length-twelve unit vector. For bounded-distance decoding, the three-error syndrome decoding of extended Golay code is the following finite search, returning the first successful candidate error:
  • If , return .
  • Otherwise, if some satisfies , return .
  • Otherwise, compute ; if , return .
  • Otherwise, if some satisfies , return .
  • If no test succeeds, declare that no error of weight at most three has this syndrome.
Every returned candidate has total Hamming weight at most three and the required syndrome. Conversely, an error of total weight at most three has a half of weight zero or one. The tests exhaust respectively , , , and , so they find every such error. Two distinct successful candidates would differ by a nonzero codeword of weight at most six, contradicting . Thus the result is unique, and the decoded word is . The condition still allows the first test when the weight is exactly three; for larger syndrome weight begin with the second test. A large syndrome weight alone does not imply more than three errors.
The decoder corrects every error of weight at most three; failure means that the received word is outside all radius-three decoding balls. Unlike its puncture, is not a perfect code: its radius-three balls cover only words. Without the three-error assumption, a successful test identifies a nearby codeword but need not identify the transmitted word.
For an arbitrary received word, a complete minimum-distance decoding fallback is to enumerate and minimize . Every error with the observed syndrome has exactly the form , so a minimizer gives a nearest codeword . Report all minimizers if there is a tie. This also decodes outside the guaranteed radius in the nearest-word sense, while making no unsupported claim that the transmitted word is determined. Thus a syndrome of weight at least three alone is insufficient for guaranteed recovery; either the three-error hypothesis or a choice among nearest words is needed.
For patient , let be the fatigue state at time years since study entry. Let the covariate vector be , representing the sex indicator, arthritis duration in years, HAQ disability score and haemoglobin measurement. Conditional on these covariates, the continuous-time multi-state model has the Markov property and generator matrix
Each allowed transition intensity has its own log-linear transition intensity model, . The zero entries exclude direct instantaneous jumps between mild and severe states, and the diagonals enforce zero row sums.
To express the estimates correctly, the printed intensities are evaluated at the sample covariate means , not at . Order the allowed transitions as . Their estimates are
with rows indexed by that transition order and columns by in
Equivalently, the uncentred intercept is . The means are not printed, so the displayed rates cannot be treated as numerical zero-covariate intercepts.
The assumptions are independent patients conditional on their covariates; correctly observed fatigue states; no unmodelled history dependence once current state and covariates are known; positive adjacent-state intensities with the specified exponential covariate dependence and no interaction terms; and a noninformative observation and censoring mechanism for the conditional state-process likelihood. With fixed covariates the rates are homogeneous in time and holding times are exponential. Covariates updated at visits are treated as piecewise constant between observations, so each such interval has a constant generator, a piecewise-constant covariate approximation. In particular this is an approximation if a quantity such as duration changes continuously between visits.
For observations , conditioning on the initial observed state, the panel-observed multi-state likelihood is a product over patients and intervals of
where is the covariate value held over that interval. Multiple unobserved jumps within an interval are integrated out by this transition matrix. For example, a mild state followed by a severe state can have positive likelihood despite , because an unobserved moderate state can intervene. The panel observations within a patient are not independent; it is the Markov property that justifies multiplying conditional transition probabilities. The piecewise-constant handling of changing covariates is specified in the msm model documentation.
The command uses the model without covariates, starts in mild fatigue at time zero, and calculates expected accumulated years in each state between times and . Let be the fatigue state and its fitted generator matrix. For the occupation time of a continuous-time Markov chain,
the expected finite-horizon occupation time is
The first equality follows by interchanging a bounded time integral and expected value, and the second uses the homogeneous continuous-time Markov chain transition matrix. The reported expectations are 7.014800 years mild, 1.724686 years moderate, and 1.260514 years severe. They sum to ten because the person occupies exactly one state at every time. All repeated entries are counted: these are not the lengths of single holding times, the durations until first reaching each state, or the probabilities of occupying the states at year ten. The interpretation of the time limits is also given in the package documentation.
Age changes during follow-up, so the generator matrix changes with time. The transition matrix must solve , with . It is generally not the matrix exponential of one constant matrix; even is not generally valid because the matrices at different times need not commute.
For example, write the age-dependent onset rate as and keep progression rate constant. Then
Even when the integrated onset rate is elementary, this remaining integral need not have an elementary closed form. Special cases can have closed forms; time dependence does not by itself prove universal impossibility.
For a tractable likelihood function, freeze age at its left-endpoint value, or a midpoint value, on each observation interval . The genetic covariate is already constant. This piecewise-constant covariate approximation gives a constant matrix on each interval and a product of closed-form interval probabilities:
Here is the observed state at , and the likelihood function is conditional on the initial state. The approximation improves when intervals are short relative to the variation in the age effect.
Write for the all-one column vector. The parity-check extension of a linear code is
The defining map is linear, so is a binary linear code. If is a generator matrix and a parity-check matrix for , then one may take
The punctured code in, say, the last coordinate is
Coordinate deletion is a linear map, so is linear. Its generator matrix is obtained by deleting the last column of . If the minimum distance is at least two, deletion is injective on , and hence has the same dimension as .
For its parity-check matrix, first use invertible row operations on to make its nonzero last column a coordinate vector. The last column is nonzero because otherwise the weight-one word supported there would belong to , contrary to . Delete the pivot row and the last column; the resulting matrix is a parity-check matrix for . Equivalently, is obtained by shortening the dual code at the deleted coordinate.
Finally, the shortened code in the last coordinate is
It is linear whenever is linear, because it is the puncture of the subspace .
Approximate changing covariates by constant values on observation intervals. The generator matrix is then constant on each interval, with transition matrix . Multiplying the relevant entries gives a conditional likelihood function for discretely observed states.
Puncturing (coding theory) Created 2026-10-03 Updated 2026-11-05
Puncturing deletes specified coordinate positions from every codeword of a block block code. Puncturing one coordinate changes a length- code into a length- code; each pairwise Hamming distance decreases by at most one.
If the original minimum distance is at least two, deleting one position cannot merge distinct codewords, so their number is preserved and the new minimum distance is either or . For example, puncturing gives . For a linear code, one may puncture its generator matrix by deleting the corresponding column, though the dimension can fall if the original distance was only one. This differs from shortening, which first restricts a coordinate value and then deletes it.
Self-dual code 2026-10-14
A linear code is self-dual when it equals its dual code under the standard dot product. For a length- code with a rank- generator matrix , this is equivalent to : orthogonality gives inclusion in the dual code, and equal dimensions give equality. Over , a generator matrix therefore generates a self-dual code exactly when .
Systematic encoding 2026-10-14
A systematic encoder retains the message symbols unchanged in designated coordinates of its codeword and calculates the remaining check symbols. For a linear code, choosing an invertible set of columns of a generator matrix and changing its row basis gives this form.