Equidistant Codes in the Grassmannian: Mathematical Structures and Applications
Explore the concept of equidistant codes in the Grassmannian space, discussing their definitions, motivation, and applications in network coding. Learn about the construction of trivial and non-trivial equidistant codes, their properties, and how they play a crucial role in error correction and distributed storage systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
June 19th, 2014 Algebra, Codes and Networks, Bordeaux Equidistant Codes in the Grassmannian Netanel Raviv Joint work with: Prof. Tuvi Etzion Technion, Israel Netanel Raviv Equidistant Codes in the Grassmannian 1 June 2014
Motivation Subspace Codes for Network Coding The Butterfly Example A and B are two information sources. A sends B sends A,B The values of A,B are the solution of: Netanel Raviv Equidistant Codes in the Grassmannian 2 June 2014
Motivation Subspace Codes for Network Coding Errors in Network Coding. A,B The values of A,B are the solution of: Even a single error may corrupt the entire message. Solution: Both Wrong Netanel Raviv Equidistant Codes in the Grassmannian 3 June 2014
Motivation Subspace Codes for Network Coding Received message Error vectors Transfer matrix Sent message Transfer matrix Setting Term Metric Set Metric Kschischang, Silva 09 known to the receiver. chosen by adversary. Coherent Network Coding Koetter, Kshischang 08 chosen by Noncoherent Network Coding adversary. Netanel Raviv Equidistant Codes in the Grassmannian 4
Equidistant Codes - Definitions Definition A code is called Equidistant if such that all distinct satisfy . Hamming Metric A binary constant weight equidistant code satisfies Subspace Metric A constant dimension equidistant code satisfies A t-Intersecting Code. Netanel Raviv Equidistant Codes in the Grassmannian 5
Equidistant Codes - Motivation Interesting Mathematical Structure Distributed Storage Netanel Raviv Equidistant Codes in the Grassmannian 6
Trivial Equidistant Codes Definition A binary constant-weight equidistant code is called trivial if all words meet in the same coordinates. t For subspace codes, similar A Sunflower. Netanel Raviv Equidistant Codes in the Grassmannian 7
Trivial Equidistant Codes - Construction Definition A 0-intersecting code is called a partial spread. If there exists a perfect partial spread of size . If , best known construction [Etzion, Vardy 2011] Construction of a t-intersecting sunflower from a spread - Trivial codes are not at all trivial Netanel Raviv Equidistant Codes in the Grassmannian 8
Bounds on Nontrivial Codes Theorem [Deza, 73] Let be a nontrivial, intersecting binary code of constant weight . Then Use Deza s bound to attain a bound on equidistant subspace codes: The bound is attained by Projective Planes: The Fano Plane The number of 1-subspaces of Netanel Raviv Equidistant Codes in the Grassmannian 9
Construction of a Nontrivial Code Julius Pl cker 1801-1868 Pl cker Embedding Idea: Embed in a larger linear space. Let whose row space is , and map it to However: Problem: is not unique. M Netanel Raviv Equidistant Codes in the Grassmannian 10
Plcker Embedding Define: For Theorem [Pl cker, Grassmann ~1860] P is 1:1. Netanel Raviv Equidistant Codes in the Grassmannian 11
Construction of a Nontrivial Code Consider the following table: Each pair of 1-subspaces is in exactly one2-subspace. 0 0 1 0 0 0 1 1 Any two rows have a unique common 1. 0/1 by inclusion Netanel Raviv Equidistant Codes in the Grassmannian 12
Construction of a Nontrivial Code Define: 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 Netanel Raviv Equidistant Codes in the Grassmannian 13
Construction of a Nontrivial Code . Lemma: is bilinear when applied over 2-row matrices. Proof: Netanel Raviv Equidistant Codes in the Grassmannian 14
Construction of a Nontrivial Code Lemma: is bilinear when applied over 2-row matrices. Theorem: Proof: Netanel Raviv Equidistant Codes in the Grassmannian 15
Construction of a Nontrivial Code The Code: 0 0 1 1 A 1-intersecting code in 0 0 0 1 1 Size: Netanel Raviv Equidistant Codes in the Grassmannian 16
Application in Distributed Storage Systems A network of servers, storing a file . Failure Resilient Reconstruction Netanel Raviv Equidistant Codes in the Grassmannian 17
DSS Subspace Interpretation [Hollmann 13] Each storage vertex is associated with a subspace . Storage: each receives for some Repair: gets such that Extract Reconstruction: Reconstruct Netanel Raviv Equidistant Codes in the Grassmannian 18
DSS from Equidistant Subspace Codes For let and Claim 1: Allows good locality. Claim 2: If are a basis, then Allows low repair bandwidth. Netanel Raviv Equidistant Codes in the Grassmannian 19
DSS from Equidistant Subspace Codes Low Low Update Complexity Bandwidth No Restriction on Field Size High Error Resilience Good Locality Netanel Raviv Equidistant Codes in the Grassmannian 20
Equidistant Rank-Metric Codes A rank-metric code (RMC) is a subset of Under the metric Construct an equidistant RMC from our code. Recall: Lemma: Construction: All spanning matrices of the form Netanel Raviv Equidistant Codes in the Grassmannian 21
Equidistant Rank-Metric Codes Linear Constant rank - Linear, Equidistant, Constant Rank RMC Netanel Raviv Equidistant Codes in the Grassmannian 22
Open Problems Conjecture [Deza]: A nontrivial equidistant satisfies Attainable by Attainable by our code . Using computer search: Netanel Raviv Equidistant Codes in the Grassmannian 23
Open Problems Close the gap: For a nontrivial equidistant Find an equidistant code in a smaller space. Equidistant rank-metric codes: Our code Linear equidistant rank-metric code in of size . Max size of equidistant rank-metric codes? Smaller? Netanel Raviv Equidistant Codes in the Grassmannian 24
Questions? Thank you! Netanel Raviv Equidistant Codes in the Grassmannian 25
