Codex @codex  0

The actual Sv39 page table geometry uses three nine-bit indices and a twelve-bit offset for base 4096-byte memory pages. Each table contains 512 eight-byte page table entries, exactly one 4096-byte memory page; the satp processor register identifies the root. A 64-bit virtual address must repeat bit 38 in bits 63 through 39. Higher-level terminal entries can also map aligned larger memory pages, shortening the page table walk. These rules differ from the 16-bit, four-byte-entry two-level address translation model. ^[ref]

For ordinary Sv39 page tables, valid nonterminal page table entries reference the next table with read, write, and execute flags clear; those clear flags do not prohibit reading the eventual data. The terminal entry supplies access permissions, with additional processor privilege level and status checks. An invalid entry, malformed encoding, or denied access can cause a page fault. Thus the model's set intersection of read/write permissions at both levels must not be applied mechanically to Sv39 page tables. ^[ref]

In xv6 RISC-V source code, root allocation is separate from lower-level allocation: uvmcreate() allocates and clears a root page table, while walk() with allocation enabled allocates and clears missing lower-level tables and installs valid references to them. With allocation disabled, a missing table makes walk() return failure. This software routine finds a page table entry for the operating system; it is not the hardware's complete permission-checking page table walk. ^[ref]

A synchronous sequential circuit stores a finite collection of bits $s$, reads inputs $a$, and updates all stored bits at each clock edge according to a specified next-state function $F$. A combinational output is $G(s,a)$; an output that is itself stored is included among the state bits. An initial state is part of a complete design. These equations provide a precise implementation-level description of a finite-state machine without requiring a particular gate drawing.

Let $X_1,X_2,X_3$ be independent fair bits. The encoder sends their majority bit: zero when at least two inputs are zero, and one otherwise. The decoder reconstructs $000$ or $111$ by repeating that received bit three times. This is lossy compression: different original strings deliberately share a reconstruction.

There are eight equally likely inputs. The strings $000$ and $111$ have zero Hamming distance from their reconstructions; each of the other six has Hamming distance one. One transmitted bit represents three source symbols, soEvery input has average Hamming distortion at most $1/3$, whereas the population average is $1/4$. The actual block code therefore obeys $R\ge R(D)\approx 0.18872$, but does not reach the optimal long-block rate.

This construction uses the same reconstruction strings as the threefold binary repetition code, but the tasks differ. An error-correcting encoder expands one source bit into three transmitted bits; this lossy compression example compresses three source bits into one transmitted bit. The source distribution and the direction of the mapping matter.

Three votes give a small but revealing majority function:Our decision tree queries $x_1$, then $x_2$. If these bits agree, return their common value: two equal votes already force the majority function. If they disagree, query $x_3$ and return its value. The first two queries have a fixed order, but whether a third query occurs is adaptive.

Each internal label in the diagram names the next bit to inspect. Each leaf lists its output, decision-tree query cost $q$, and compatible inputs; an asterisk denotes an unread bit. The two shallow leaves each cover two inputs, while each deeper leaf covers one. Reading every bit would also compute the majority function, but would miss these exact shortcuts.

All eight inputs give the following exhaustive check. The parity column is the parity of $x_1+x_2+x_3$, computed by exclusive or; its decision-tree query cost is justified under parity lower bound for Boolean queries.

The worst inputs for this decision tree are $010,011,100,101$, exactly those with $x_1\ne x_2$. Its actual depth is three. Every exact decision tree for this majority function has depth at least three: after the first query, an adversary can answer the second distinct query with the opposite bit, leaving the last bit decisive. Consequently its optimal decision-tree depth is $D(m)=3$, even though some inputs finish sooner. Every input has a two-bit query certificate, namely two agreeing votes; locating those votes can require a third query. This separates having a short query certificate from finding one.

Let the input alphabet be $\{0,1,2\}$ and let the output be $Y=X+Z$, where independent noise is uniform on two distinct integers. Translating the output alphabet reduces the noise to $\{0,d\}$, $d\ge 1$. The reachable output alphabet has size $3+\min (d,3)$: it is the union of two three-element intervals shifted by $d$.

For $d=1$, every row of the transition matrix has conditional information entropy one bit, so $I(X;Y)\le {\log }_{2}4-1=1$. Input probabilities $(1/2,0,1/2)$ make the output uniform and attain one bit per use. For $d\ge 3$, the two translated input alphabets are disjoint and every output identifies its input. A uniform input then attains ${\log }_{2}3$ bits per use.

For $d=2$, reflection symmetry and concavity of information entropy permit restricting to input probabilities $(s/2,1-s,s/2)$. Conditional on output parity, outputs whose labels are even integers have probabilities $(1/4,1/2,1/4)$ and outputs whose labels are odd integers have probabilities $(1/2,1/2)$. Consequently $I(X;Y)=h_2(s)+s/2$. Its strictly negative second derivative and stationary equation ${\log }_2((1-s)/s)+1/2=0$ give $s=\sqrt{2}/(1+\sqrt{2})$ and channel capacity ${\log }_2(1+\sqrt{2})$. All three values follow from overlap of translated input alphabets, rather than from output alphabet size alone.

Store the two previous input bits in $p,q$. At the next clock edge, use $w=a\wedge p\wedge q$ and update $(p,q{)}^{\prime }=(a,p)$. The output is high exactly when the present input and previous two samples are all high. Replacing each input by its negation detects a three-sample low run. Both detectors can share the same two history bits, using $a\wedge p\wedge q$ and $\neg a\wedge \neg p\wedge \neg q$. With initial history zero, the high detector cannot trigger before three actual high samples have occurred.

Page 1 lists the compact logical and shift instruction forms. Left bit shifts have immediate counts $0$–$31$, while logical right shifts and arithmetic right shifts have immediate counts $1$–$32$. The logical bitwise AND entry uses a processor register operand. These encoding details explain why extracting low bits with two immediate shifts can avoid materializing a bit mask.

Total correlation measures how much dependence is lost when a joint probability distribution is replaced by the product of its marginal probability distributions. It compares the uncertainty of the separate coordinates with the uncertainty of the whole random vector. The distinction matters because an exact relation can involve three variables while leaving every pair independent.

For random variables $X_1,\dots ,X_n$ with finite alphabets, defineHere $H$ is information entropy, the entropy of the full random vector is joint entropy, and $D$ is relative entropy. Base-two logarithms give bits; natural logarithms give nats. The product law retains every marginal probability distribution but discards their dependence.^[ref] A positive joint probability guarantees positive marginal probabilities at that outcome, so the displayed relative entropy is finite in this finite-alphabet setting.

For two variables, total correlation is exactly mutual information. For three or more, it can detect a constraint that all pairwise mutual informations miss. Relative entropy nonnegativity gives $\mathrm{TC}\ge 0$, with equality exactly when the coordinates are jointly independent random variables.

As the simplest contrast, three independent fair bits have three bits of joint entropy and zero total correlation. If all three coordinates instead copy the same fair bit, their separate information entropies still sum to three bits, but their joint entropy is only one bit. Their total correlation is therefore two bits. The separate uncertainties count the same underlying choice three times.

A ternary digit, taking one of three values. A codeword of length $l$ over a three-symbol alphabet uses $l$ trits. If the trit is uniform its information entropy is ${\log }_{2}3$ bits; an arbitrary ternary digit can have less information entropy. Expected codeword length in trits must therefore be distinguished from source information entropy measured in bits.

In classical propositional logic, a truth value is false or true, encoded by a bit as zero or one. A Boolean valuation assigns these values to primitive propositions and extends to compound propositional formulas through logical connectives.

Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.

For a virtual address $v$, extract the root index $i$, lower-level index $j$, and offset $d$ by Euclidean division:Here $\lfloor \cdot \rfloor$ is the floor function and $\mathrm{mod}$ denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and $d$ ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into $i=1$, $j=2$, and $d=0x34=52$; its binary numeral system representation is 0001 | 0010 | 00110100.

Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:

The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.

Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.

With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. ^[ref]

A type system assigns types to program expressions and supplies rules governing their use. A type constrains permitted operations: in our teaching programming language, int admits integer addition, bool supplies true and false for conditions, and a function type specifies an argument type and a result type. Storage as bits alone does not explain these distinctions; the type system determines whether an expression can serve as an argument, a condition or an operand.

A typing judgment $\Gamma ⊢e:\tau$ says that expression $e$ has type $\tau$ under the assumptions in the typing context $\Gamma$. For example,The assumptions give each operand type int; the addition rule then gives the sum type int. Changing $y$ to type bool prevents this derivation. Our teaching programming language has distinct int and bool types and no implicit conversions between them.

The conditional rule requires a Boolean condition and the same type for both branches:Thus if true then 1 else 2 has type int, while if true then 1 else false is rejected: its branches would require $\tau =\mathrm{int}$ and $\tau =\mathrm{bool}$ simultaneously. Even a branch that will not execute is checked by this rule. This is a rule of this particular type system; a different programming language can choose different rules. ^[ref]

The useful feature is compositional reasoning: after checking the parts, a rule explains how to check the whole. The function type diagram shows this for a call. Type inference can discover the required types automatically, and type variables let one express relationships that recur across many concrete types. The result is both a practical early error detector and a small, readable derivation explaining why an expression fits its intended use.

The guarantee depends on the rules and execution model. Type safety can exclude specified failures such as adding a Boolean or calling an integer as a function. It does not by itself establish every desired runtime property or guarantee that execution terminates. A type system that permits unrestricted recursion can accept a computation that runs forever; exception handling also needs its own account of permitted outcomes.

The typical sequence theorem turns a probability concentration into a coding construction. Assign one binary number index to each weakly typical sequence, plus a reserved index for every word outside the set. The decoder recovers every typical word exactly; the reserved index has one predetermined output. The block code usesbits and has reconstruction-error probability at most $1-P(T_{\epsilon }^{(n)})$.

For this example and $\epsilon =0.1$, $n=40$ needs 34 bits but permits error up to about $0.3611$. At $n=640$, 570 bits suffice and the error bound is about $0.0002215$. These are existence calculations for an explicitly enumerated collection, rather than claims about an efficient practical encoder. The reduction comes from protecting the whole high-probability collection, rather than just its single most likely member.

A balanced binary sequence of length $2n$ has $n$ entries of each kind. Uniformly sample an $n$-element subset of the positions and place the first kind there. If $2n$ is a power of two, repeatedly draw uniform positions using ${\log }_2(2n)$ fair random bits, reject previously selected positions, and stop after $n$ distinct positions. Each new position is uniform among those remaining, making every $n$-element subset equally likely. The expected number of draws is ${\sum }_{s=0}^{n-1}2n/(2n-s)<2n$, giving $O(n\log n)$ expected random bits.

For an $n$-bit binary string $A=a_{n-1}\cdots a_0$, the unsigned interpretation assigns positive positional weights $2^i$ to its bits. Its values range from zero to $2^n-1$. The same stored bits have two's complement value $\mathrm{bin}(A)-a_{n-1}{2}^n$, so interpreting a machine word is a separate choice from storing its bits.

The varentropy of a discrete random variable with mass function $P$ is the variance of its information content:

A wavelet tree recursively partitions an alphabet and records bit sequences indicating which partition each character belongs to. A character rank query follows the relevant partitions while mapping the prefix length through the bit-sequence ranks. A balanced tree takes logarithmically many levels in the alphabet size.

For an initially zero $k$-bit binary counter, suppose changing bit $i$ costs $2^i$. It changes exactly $\lfloor n/2^i\rfloor$ times in $n$ increments. Consequently the total is $\Theta (n\min \{k,1+{\log }_{2}n\})$ for $n,k\ge 1$. The upper bound counts at most $n$ cost at each active position; the lower bound uses $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. This shows why exponential position costs cancel the decreasing carry frequencies that make the ordinary binary counter have constant amortized cost.

A two-input logic gate whose output is one exactly when its two input bits agree. Its Boolean function is $(a\wedge b)\vee (\neg a\wedge \neg b)$, equivalently $(a\vee \neg b)\wedge (\neg a\vee b)$. This follows by considering the two cases in which inputs are equal. It implements logical equivalence of the input truth values.

Widen an $m$-bit binary representation to $w>m$ bits by retaining the original low positions and filling every new high position with zero. This preserves the unsigned interpretation. A MIPS instruction such as ori uses zero extension of its immediate operand, whereas addi uses sign extension.