summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
-rw-r--r--Ethernet107
-rw-r--r--math/algebra71
 diff --git a/Ethernet b/Ethernetindex 6b4be44..6240871 100644--- a/Ethernet+++ b/Ethernet@@ -1,14 +1,15 @@ ======== Ethernet ========+:Author: Bryan Newbold -.. warning:: Under progress!+.. contents:: History =======-Bob Metcalfe first described the ethernet system in a memo while working at-the Xerox Palo Alto Research Center in 1973 ([oreilly]_). It was based on-the earlier *Aloha* system developed by Norman Abramson at the University of+Bob Metcalfe first described the ethernet system in a memo while working at the+Xerox Palo Alto Research Center in 1973 ([oreilly]_). It was based on the+earlier *Aloha* system developed by Norman Abramson at the University of Hawaii. *Aloha* was a radio network for inter-island communications. Structure@@ -34,16 +35,114 @@ Checksum 32 The preamble originally served as a "warm up" period for hardware to stabilize and prepare for the rest of the frame. + The last 8 bits are the preamble are a particular "start frame delimiter"+ pattern to help hardware notice the beginning of signal transmission.+ .. topic:: Source and Destination addresses Manufacturers are given a 24 bit id (first half), and are expected to ensure the uniqueness of the second half of each device's address. + If the first bit of the destination is high (1), the destination is+ multicast; if low (0), then unicast. Under IEEE, if the second bit is high,+ global administration rules should be followed, and if low, local+ administration rules should be followed.+ The IEEE-SA (Standards Association) delegates addresses. .. topic:: Checksum The checksum (or Frame Check Sequence) is a Cyclic Redundancy Checksum. +Inter-Frame Gap+~~~~~~~~~~~~~~~~~+The Inter-Frame Gap (IFG) is a pause in between signal frames; it is 96+bit-times long.++.. _collision:++Collisions+=============+Collision management is the heart of Ethernet; a collision occurs when two+devices try to transmit at the same time and their signals overlap and the+transmission is unreadable. This problem is made worse the further apart+stations are because it takes longer for signal fronts to propagate, so there+is a longer overlap period when the first device has started transmitting but+the second hasn't noticed and may start transmitting on its own. The network+size (in distance, not nodes) is determined by the maximum collision period+(also called slot time). This period is 512 bit-times, so usually the faster a+network is, the smaller it should be (in distance); at gigabit speeds the+slot is expanded, see Speeds_.++Under Ethernet, if any device detects a collision, it sends out a 32 bit+"collision enforcement jam signal" to ensure that all devices notice the+collision. Then each device that wishes to transmit waits a random amount of+bit-times r before transmitting again. If there is another collision, a new+r is randomly chosen with a larger maximum; up to 15 retries are allowed before+the devices will give up and drop the frame. The constraints for the random+backoff time r are $0\leq r \leq 2^k$:latex:, where r is in bit times and+k is the number of retry attempts up to 10 (for 11th to 15th retries, use +k=10).++Speeds+=========+At 10mb, bit time is 100ns (nano-seconds); at 100mb, 10ns; at 1gb, 1ns.++At gigabit speeds, the slot time would limit network size to 20 meters, so+it gets padded with a null "carrier extension" signal to 4096 bits (512 bytes). +On high speed half-duplex gigabit links (which are rare!), frame bursting is+a technique to allow several small data frames to be transmitted at the same+time: one frame is sent regularly to capture the channel, then up to 65536+bit times of short non-carrier extended (only IFG) frames are sent, then +a single last regular frame is sent.++Phrases+=========++Auto-negotiation+ Optional protocol for direct links (eg, from switch to switch) to + determine network speed. Can be reinitiated by dropping and restarting+ the link.++802.1+ IEEE working group for higher level networking.++802.2+ IEEE working group for "logical link control" (LLC), which is related+ to the type/length frame field.++802.3+ For _CSMA/CD LANs++802.5+ For Token Ring LANs++CSMA/CD Protocol+ Stands for Carrier Sense Multiple Access/Collision Detect. The two main+ implementations are DIX (DEC-Intel-Xerox) and IEEE. (Can't remember how+ this works...)++VLAN+ Optional 4-byte field in between "source" and "type" fields. The first+ two bytes are a valid type field; this increases the max length to+ 1522 bits. Only used by switches.++Channel Capture+ This phenomena is a result of _collision management. After a few + sequential collisions, the device that ultimately transmits first gets+ its backoff reset to zero, while all other devices retain a high backoff;+ this means the first device is much much more likely to retransmit again+ faster than any of the others, and if it has a lot of frames to send it+ will dominate the carrier until it is done transmitting.++Jabber+ When a broken station/device keeps a carrier open and prevents other+ transmissions.++PAUSE+ A PAUSE frame is a MAC control (higher level, type 0x8808) frame which+ causes switches to stop for up to 65536 slot times to allow a switch or+ station to clear its buffers.+ .. [oreilly] Ethernet: The Definitive Guide:title:, by Charles Spurgeon. O'Reilly, 2000diff --git a/math/algebra b/math/algebranew file mode 100644index 0000000..b337a2e--- /dev/null+++ b/math/algebra@@ -0,0 +1,71 @@+====================+Algebra+====================++.. note:: Most of the definitions and notation in the section are based on [rudin]_ or [meserve]_++.. list-table:: Closure of binary operators on given sets of numbers+ * Operation+ - :latex:$+$+ - :latex:$\times$+ - :latex:$-$+ - :latex:$\divide$+ - :latex:$^$+ - :latex:$\sqrt{\text{ }}$+ * Positive Integers+ - Y+ - Y+ - N+ - N+ - Y+ - N+ * Positive rationals+ - Y+ - Y+ - N+ - Y+ - Y+ - N+ * Rationals (and zero)+ - Y+ - Y+ - Y+ - Y+ - Y+ - N+ * Reals wrt positive integers+ - Y+ - Y+ - Y+ - Y+ - Y+ - Y+ * Complex numbers+ - Y+ - Y+ - Y+ - Y+ - Y+ - Y++Definitions+=============++*involution*+ to raise a number to a given power++*evolution*+ to take a given root of a number++*associative*+ :latex:$(a+b)+c=a+(b+c)$++*comutative*+ :latex:$a+b=b+c$++*distributive*+ :latex:$(a+b)c=ac+bc$++.. [rudin] Principles of Mathematical Analysis (3rd ed):title:, by Walter Rudin. McGraw-Hill, 1976++.. [meserve] Fundamental Concepts of Algebra:title:, by Bruce Meserve.diff --git a/math/books to read b/math/books to readnew file mode 100644index 0000000..ba75d8e--- /dev/null+++ b/math/books to read@@ -0,0 +1,33 @@+===============================================+Math books that look interesting+===============================================++On formally undecidable propositions of Principa Mathematica and related systems:title:, by Kurt Godel. ++Computability and Unsolvability:title:, by Martin Davis. ++Mathematical Foundations of Information Theory:title:, by A.I. Khinchin. ++Calculus of Variations with Applications to Physics and Engineering:title:, by Robert Weinstock. ++Relativity, Thermodynamics, and Cosmology:title:, by Richard Tolman.++Mathematics Applied to Continuum Mechanics:title:, by Lee Segel.++Optimization Theory and Applications:title:, by Donald Pierre.++The Variational Principles of Mechanics:title:, by Cornelius Lanczos.++Tensor Analysis for Physicists:title:, by J.A. Schonten.++Investigations on the Theory of Brownian Movement:title:, by Albert Einstein.++Great Experiments in Physics:title:, ed. by ???.++Curvature and Homology:title:, by Samuel Goldberd.++The Philosophy of Mathematics:title:, by Stephan Korner.++The Various and Ingenious Machines of Agostino Ramelli:title:, by A. Ramelli (!).++Experiments in Topology:title:, by Stephan Barr.diff --git a/math/good books b/math/good booksnew file mode 100644index 0000000..bc3efe5--- /dev/null+++ b/math/good books@@ -0,0 +1,5 @@+==========================================+Recommended Math Reading+==========================================++BLANKdiff --git a/math/integers b/math/integersnew file mode 100644index 0000000..b946ce8--- /dev/null+++ b/math/integers@@ -0,0 +1,5 @@+====================+Integers+====================++definition via Peano's Postulates: meserev 1-4diff --git a/math/logic b/math/logicnew file mode 100644index 0000000..65ceba9--- /dev/null+++ b/math/logic@@ -0,0 +1,18 @@+=======================+Mathematical Logic+=======================++.. note::+ Incomplete; in progress++definition of induction: meserev 1-4++Proofs+===========++Indirect Proof: "reductio ad absurdum"+ Show a paradox or impossibility in all cases by assuming the proposition + is false; then the proposition is true.++Proof by elimination+ Propose a complete set of propositions and remove all but one.diff --git a/math/numbers b/math/numbersnew file mode 100644index 0000000..541d174--- /dev/null+++ b/math/numbers@@ -0,0 +1,54 @@+========================+Numbers+========================++.. note::+ incomplete++.. note:: + Most of the definitions and notation in the section are based on [rudin]_ or [meserve]_++.. contents::++*incommensurable*+ objects are incommensurable when their ratio isn't rational++Real Numbers+==================+The *real numbers* are defined via Dedakind cuts in [rudin]_, or [meserve]_ +(1-12).++Complex Numbers+==================+The *complex numbers* are constructed as an ordered pair of real numbers.++Algebraic and Transendental Numbers+===============================================+*Algebraic numbers* are solutions of polynomials, such as x in+:latex:$a_0 x^n + a_1 x^{n-1} + a_2 x^{n-2} + ... a_n = 0$, where all a are+real numbers. *Transcendental numbers* are not solutions to any such +polynomials.++All real numbers are either algebraic or transcendental. ++Some algebraic numbers aren't real (such as :latex:$i = \sqrt{-1}$). They+can be rational or irrational. All transcendental numbers are irrational;+some are not real.++Exersize: is the square root of 5 algebraic or transcendental?++e+========+:latex:$e = \lim_{x \rightarrow 0} (1+x)^{\frac{1}{x}}$++Infinities+==================+*aleph-zero* (:latex:$\aleph_0$) is the countably infinite set.++Positive integers, integers, and rational numbers are all countably infinite.++It is unproven that the real numbers are *aleph-one* (:latex:$\aleph_1$).++.. [rudin] Principles of Mathematical Analysis (3rd ed):title:, by Walter Rudin. McGraw-Hill, 1976++.. [meserve] Fundamental Concepts of Algebra:title:, by Bruce Meserve.diff --git a/math/sets b/math/setsindex 6d75a55..42eb831 100644--- a/math/sets+++ b/math/sets@@ -2,11 +2,46 @@ Sets ==================== -.. warning:: Under progress!+.. note:: Most of the definitions and notation in the section are based on [rudin]_ or [meserve]_ -.. note:: Most of the definitions and notation in the section are based on [rudin]_+Basics+=============+If every element :latex:$a \in A$ is also :latex:$a \in B$, then we call+A a *subset* of B and write :latex:$A \subset B$. If there are elements of B+which are not elements of A, then we call A a *proper subset* of B. -If :latex:$A \supset B$ and :latex:$B \supset A$ we write :latex:$A = B$; otherwise :latex:$A \neq B$.+If :latex:$A \supset B$ and :latex:$B \supset A$ we write :latex:$A = B$;+otherwise :latex:$A \neq B$. -.. [rudin] Principles of Mathematical Analysis (3rd ed):title:, by Walter Rudin.- McGraw-Hill, 1976+The null or empty set, which has no elements, is a subset of all others.++A relation on a space of sets S is something that can be definted as either +true or false (holding or not holding) for any binary pair in S.++Binary Operators+==================+Binary operators defined on a set apply to any two elements of that set; order+may or may not be important. A set is *closed* with regards to a binary+operator if it contains the result of the binary operator. A set is *uniquely+defined* with regards to a binary operator if the result of the operator on two+elements of the set is unique from the results from all other pairs of+elements.++Some equivalence relations are +:latex:$\identity$ (NOTE: = with three lines) (*identity*);+:latex:$\congruence$ (NOTE: = with tilde on top) (*congruence*; eg of +geometric figures); and +:latex:$~$ (NOTE: tilde) (*similarity*; eg of geometric figures).++Some properties of equivalence relations are++*reflexive* + if :latex:$a=a$ is true for all a+*symetric* + if :latex:$a=b$ implies :latex:$b=a$+*transitive* + if :latex:$a=b$ and :latex:$b=c$ implies :latex:$a=c$++.. [rudin] Principles of Mathematical Analysis (3rd ed):title:, by Walter Rudin. McGraw-Hill, 1976++.. [meserve] Fundamental Concepts of Algebra:title:, by Bruce Meserve.diff --git a/restructured text cheatsheet b/sheets/rstindex e105cba..e105cba 100644--- a/restructured text cheatsheet+++ b/sheets/rst